S3E15: Single-pass Janus sort

In this episode we investigate the development of an algorithmic heuristic template, which, by definition, is an entity that can be reused in different contexts and/or settings. To that end we, first, use the (reusable) idea of two runners chewing on a given input (linear) container, an array, starting from two diametrically opposite extremities of that container and moving in the opposite directions toward each other at the same rate of speed in order to construct an algorithm for detecting whether the given input container is a palindrome or not. Next, we take that idea of two runners and export it into an algorithm for reversing the contents of the given container. Across the above two applications of the idea of two runners processing a given input container from its two diametrically opposite ends we spot an implicit invariant - the elements of the input container that are acted on are equidistant from the (logical) vertical axis of symmetry of such a container. Thus, in both cases both runners move through the input container at the same rate of speed. Next, we export the idea of two runners into an algorithm that can be used in order to sort the input array into two non-intersecting piles of two distinct types of objects. This time, however, we notice that the two runners that served us so well so far have to move through the input container "independently" of each other. Lastly, there is yet another beautiful application of the idea of having two runners in the race to the problem of detecting a cycle in a possibly misshaped linked list. For now, we leave this problem as "an exercise to the viewer" but we will come back to and solve that problem in Season 3 Episode 19. Stay tuned.