In Place Quick Sort

This sorting algorithm uses a "divide and conquer" strategy. "In Place" means this particular quick sort strategy never creates a new array of data and is more efficient in terms of memory usage. It first locates a "pivot" (using the Median of Three strategy). Once the pivot is found, it is moved to the left-most position in the partition. A left-wall iterates over the partition, starting from just right of the pivot. When it encounters an element that is greater than the pivot, it stops. A right-wall then iterates over the partition starting from the farthest right element in the partition. When it encounters an element less than the pivot, it stops. The current elements of the left and right walls swap. This process continues until a new left and right partition are created. The new left and right partitions are inturn separated again, by finding a new pivot, iterating through the partition using a left-wall and right-wall, resulting in two more partitions. This process repeats recursively until a partition is either already sorted, or contains fewer than 3 elements. If a partition contains fewer than 3 elements, the partition is sorted using insertion sort to boost the overall efficiency of the Quick Sort algorithm.

Green highlights the potential pivots (during the Median of Three strategy), which are quickly reduced to the choosen pivot.

Yellow indicates the position of the left and right walls as they iterate over the elements of the currently sorting partition.

Red indicates where the left-wall and right-wall swap elements with one another (creating quick-sorted new left and right partitions).

Orange indicates partitions sorted using insertion sort (for those partitions that have fewer than 3 elements).

Your browser does not support HTML5 :(