A divide-and-conquer algorithm that partitions entries relative to a pivot, recursively sorts the smaller and larger partitions, and combines their results. A three-way partition keeps all equal keys in a central bucket. Correctness follows from the partition order and recursive correctness; excluding the pivot from child inputs provides decreasing finite lengths. The choice of pivot controls balance and therefore running time.
Partitioning into keys smaller than, equal to and greater than the pivot. Only the smaller and greater partitions need recursive sorting. Keeping the common partition helper in both a direct sorter and a tree-building factorisation ensures that flattening the tree introduces no extra key comparisons.
Articles by others on the same topic
Quicksort is a highly efficient sorting algorithm and is based on the partitioning principle. It was developed by the British computer scientist Tony Hoare in 1960. Quicksort is widely used for its efficiency and is particularly effective for large datasets. The algorithm follows a divide-and-conquer strategy, which can be broken down into the following steps: 1. **Choose a Pivot**: Select an element from the array to serve as the pivot.