Quick Sort

Average time complexity - O(n * log(n))

Best-Case time complexity - O(n * log(n))

Worst-Case time complexity - O(n^2)

Worst-case space complexity - O(n)

Quick Sort is an intuitive algorithm that works by choosing pivots. It chooses a pivot element, then moves every element smaller to than the pivot to its left, and every element greater to its right. It then recursively calls itself on each of those "piles". My implementation uses the last element in the array as the pivot point.

Say we have this array:

4, 1, 5, 2, 3

Quick Sort would use the last item, in this case 3, and use that as its pivot. It would first move all elements lower than 3 to its left. These are 1 and 2, and they are in this order in the array itself.

1, 2

It then recursively calls itself on this, using 2 as a pivot.

1

There's only one element, so it returns.

1, 2

Now it calls itself on the right half, and moves all elements greater than 2 to its right. There is nothing, so it returns. The previous call also returns back to the bottom level call.

4, 1, 5, 2, 3

Notice that nothing has changed. This is because all elements less than 3 were already in the array before it. Now it calls itself again, and moves all items greater than 3 to its right. This is 4 and 5.

4, 5

Now the last element is 5. It calls itself on that to move all elements less than it to its left.

4

4 happens to already be on its left, so it returns without needing to move anything. If 5 had come before 4, then it would have moved 4 before 5.

4, 5

Now it calls itself to move all items greater than 5 to its right. There's nothing, so it returns, and that level also returns to the top level.

1, 2, 3, 4, 5

The sort is now complete, as all recursive calls have completed.