Quicksort

Animated visualization of the quicksort algorithm. The horizontal lines are pivot values

Quicksort is a sorting algorithm that is used to sort items in a list. It was created by Tony Hoare in 1959, and it is still widely used today. Quicksort splits the list into two parts, a smaller one and a larger one, and then continues to split those parts into more parts, making the list more and more sorted along the way. It is a comparison sort, because it chooses a point in a part of the list and then compares it with all the other points in that part of the list.

Algorithm

1. If there is only one item in the list, or no items, stop because we don't need to sort anything.
2. Pick any item in the list, then put all the items smaller than it to the left and all items larger than it to the right.
3. Do this again on the left side.
4. Do this again on the right side.

The picked item is called the "pivot", and the process of moving items to the correct side by comparing them to the pivot is called "partitioning". Often the leftmost item is chosen as the pivot. Since the algorithm runs the same exact algorithm on the two partitions that were created by the comparisons to the pivot, the algorithm is recursive. Note that this algorithm will keep on partitioning the list into smaller lists, and splitting those smaller lists into even smaller lists. Each time it does this, it will choose a new pivot within the smaller list and compare the items inside. The base case is when the algorithm reaches a list with only one item, in which it just stops because one item does not need to be sorted.