Quicksort

noun

say it: “KWIK-sort” /ˈkwɪksɔːrt/

A sort that picks a pivot, puts smaller items on its left and the rest on its right, and sorts each side the same way.

What is quicksort?

Quicksort picks one item as the pivot, puts the items smaller than it on its left and the rest on its right, then sorts each side the same way. When pivots land near the middle it is O(n log n) and usually the fastest sort there is. When they keep landing at an end, as with the last item of an already sorted list, it slows to O(n²), so real quicksorts pick a random pivot.

In a sentence

  • “On the already sorted list, quicksort with the last item as pivot slowed to 124,750 comparisons.”

Level: Journeyman · More Data Structures terms at this level

Updated