Quick Sort Step-by-Step + Pros/Cons vs Other Sorts

Step-by-Step Example $A=[38,27,43,3,9,82,10]$, pivot last element

1. Partition [38,27,43,3,9,82,10] pivot10 → i scan → final swapped → [3,9,10,38,27,82,43] pivot index2
2. Left [3,9] pivot9 → already [3,9]
3. Right [38,27,82,43] pivot43 → partition → [38,27,43,82] → left [38,27] pivot27→[27,38] , right [82]
   Sorted [3,9,10,27,38,43,82]

If using Hoare with median-of-three pivot choice, fewer worst cases.

Algorithm (as in Q14)

QuickSort(A,l,h): if l<h: p=Partition(A,l,h); QuickSort(A,l,p-1); QuickSort(A,p+1,h)

Complexities (see Q14): Best/avg $\Theta(n\log n)$, worst $\Theta(n^2)$.

Advantages

• In-place, low constants, cache-friendly → fastest in practice on arrays.
• Average $O(n\log n)$, tail recursion can be bounded to $O(\log n)$ stack.
• Good for large datasets, easily parallelizable.

Disadvantages

• Not stable (equal elements may reorder).
• Worst $O(n^2)$ on sorted/duplicate input if naive pivot (mitigated by randomized/median pivot).
• Not good for linked lists (needs random access; Merge Sort better).
• Recursion depth risk stack overflow on worst case.

Comparison

Sort	Avg	Worst	Space	Stable	In-place
Quick Sort	$n\log n$	$n^2$	$\log n$	No	Yes
Merge Sort	$n\log n$	$n\log n$	$n$	Yes	No
Heap Sort	$n\log n$	$n\log n$	1	No	Yes
Insertion	$n^2$ avg	$n^2$	1	Yes	Yes

Conclusion: Use Quick Sort (randomized) for arrays when average speed matters; Merge Sort when stability or guaranteed $n\log n$ needed.