Turk sort algorithm - jgrigorjeva/push_swap GitHub Wiki

This algorithm was my second choice because it seemed more complicated than radix sort. Unfortunately, radix sort did not yield good enough results to achieve the highest score (based on the project description, it seemed unlikely to pass at all). The algorithm is described here and here, so I won’t repeat the full explanation. However, I did make a small modification.

The Modification

The algorithm, as described in the linked articles, assumes that after selectively pushing most numbers to stack B, three numbers should remain in stack A. These three numbers are then sorted using a hardcoded "three sort" function, after which the numbers from stack B are pushed back into their correct positions in stack A. This step seemed to add unnecessary complexity, so I omitted it. Instead, I continued selectively pushing numbers to stack B until stack A was empty. After that, only a few rotations might be needed to position the largest number at the top of stack B. At this point, stack B is sorted in descending order, and all the numbers can simply be pushed back to stack A. The results were good enough to pass the project with 100 %, but I did not test it against the original version. Feel free to do so :)