Hadron DaVinci

Quick Sort Tutorial

21 May 2021 - Hadron DaVinci

Example

Sort the given array with Merge Sort:

A = [5, 2, 4, 6, 1, 3]
quick_sort(A)
assert(A) == [1, 2, 3, 4, 5, 6]

Method

1. Insert Sort when array is small
   • less than 4 items
2. Find Pivot using Median of Three (MO3)
   • find median or first, last, and middle elements
3. Swap Pivot with Last element
4. Swap GTP with LTP repeatedly while GTP index < LTP index
   • GTP = greater than (or equal to) Pivot
   • LTP = less than Pivot
5. Swap Last GTP with Pivot
6. Quick Sort Left of Pivot
7. Quick Sort Right of Pivot

Complexity

Time Complexity: N log(N)
Space Complexity: 1
Unstable

Code

method1.py