Quick Facts

  • Comparison sorting algorithm.
  • Uses divide-and-conquer approach.
  • Utilizes a pivot. Sorting all numbers in the partition less than the pivot to the left, and all numbers greater to the right.
  • Usually \(O(n*logn)\) runtime. But can be \(O(n^2)\) on sorted list with pivot chosen as the first or last index.
  • Consumes \(O(logn)\) space for recursive stack calls.

Using Lomuto’s partitioning scheme


Leave a Reply