Like the Selection algorithm, Partition is another algorithm closely related to sorting. Given an array of values, Partition splits the array into sections. For example, C++ nth_element function rearranges the array in such as way, that the n-th element has a value as if the array has been sorted. Also, array elements to the left of the n-th index are all smaller than the value at the n-th index, and the array elements to the right of the n-th index are equal to or larger than the value at the n-th index.

In other words, the element at the n-th index partitions the array into smaller values on the left and larger values on the right.

Extending this concept to more than one partition element, where one partition element leads to two partition regions (left and right), with two partition elements results in three partition regions. Three partition elements leads to four partition regions. Each partition region has elements whose values are in between the two partition elements that are on the left and right sides of that region. However, the elements within a partition region are not in a sorted order.

Using Comparisons

Traditional method used for Partitioning is based on the QuickSelect algorithm, which uses partitioning.

Using Radix

In-place MSD Radix Sort is linear-time O(N) is a good starting point. However, it does too much work by sorting all array elements. To create a partition algorithm out of it, after performing the first level of the MSD Radix Sort, based on the most significant digit, recurse only into those bins where the partitioning indexes are.