The Push swap project is a simple algorithm project. A "stack" with n amount of non-repeating random integers has to be sorted with the help of another "stack". The goal is to find a solution with the lowest amount of operations possible. Although they are called stacks in this project, they aren't limited to LIFO. They are much similar to deques in the sense that by rotating both the top and bottom can be accessed.

• sa (swap a): Swap the first 2 elements at the top of stack a.
• sb (swap b): Swap the first 2 elements at the top of stack b.
• ss : sa and sb at the same time.
• pa (push a): Take the first element at the top of b and put it at the top of a.
• pb (push b): Take the first element at the top of a and put it at the top of b.
• ra (rotate a): Shift up all elements of stack a by 1. First becomes last.
• rb (rotate b): Shift up all elements of stack b by 1. First becomes last.
• rr : ra and rb at the same time.
• rra (reverse rotate a): Shift down all elements of stack a by 1. Last becomes first.
• rrb (reverse rotate b): Shift down all elements of stack b by 1. Last becomes first.
• rrr : rra and rrb at the same time.

• 32 Stack
• 100 Stack
• 500 Stack

It is recommended to also have a look at the links at the bottom, since they show the sorting of sorted stacks, which makes it a lot clearer of what the algorythm is doing.

Because of the uniqueness of the task, conventional algorithms were hardly optimal. Most conventional sorting algorithms focus on fast computation time and have access to all the data. Computation time is of no concern in this project, and "looking" for specific numbers by rotating the stack is a very expensive operation.
Depending on the top number in A one of the following operation is done:

Once this has been done for all the Numbers in A. The 50% remaining numbers in A will do the same operation again but this time without the option to rotate A. This splits the numbers into 4 Groups. These groups get treated as a single number for the rotation of the operation.
Example:

• 128 Numbers in A
• 32 Groups in B
• 8 Groups in A
• 2 Groups in B
• 1 Group in A

This results in a single group in A. Which means that if the specific number always got pushed into the correct group it will result in a sorted stack. Instead of calculating the correct group by hand, the whole operation was reversed.
A very intuitive approach would be to choose the groups by number size, for example for 100 numbers first splitting them into group 1-25, 26-50, 51-75, 76-100. The problem is that this would result in groups being in the wrong order later on. Which would always require rotations over groups to get the correct location to the top.

Instead, the algorithm starts with a sorted stack, doing exactly those operations and saving the groups of the numbers after doing it. Visualizations can be found here:

• 32 Stack
• 512 Stack

A few optimizations have been used, for example only splitting into 2 groups when needed and sorting the last group of 8 numbers manually.

Both n and Operations are in k
For "low" amount of numbers the amount of operations is roughly n * 13, however without the optimizations the amount of operations is:
(log(n) / log(4)) * 1.5n
The big O notation should be O(n log n)
During the evaluation, only very small stacks are tested.
100 will result in something very close to 700 operations.
500 is something around 4000 operations
Since there are still minor bugs in my implementation, it will result in slightly higher numbers.