Quick Sort

merge sort uses a lot of extra space, quick sort is in-place. quick sort is also faster in practice.

Randomized Quick Sort

Additional Space Required

Lower Bound for Comparison Based Sorting