Feb. 21, 2014, 5:40 p.m. by Rosalind Team

**Topics**:
Sorting

Comparing the algorithms for sorting and “Median” finding we notice that, beyond the common divide-and-conquer philosophy and structure, they are exact opposites. “Merge Sort” splits the array in two in the most convenient way (first half, second half), without any regard to the magnitudes of the elements in each half; but then it works hard to put the sorted subarrays together. In contrast, the median algorithm is careful about its splitting (smaller numbers first, then the larger ones), but its work ends with the recursive call.

*Quick sort* is a sorting algorithm that splits the array in exactly the same way as the
median algorithm; and once the subarrays are sorted, by two recursive calls, there is nothing
more to do. Its worst-case performance is

Source: Algorithms by Dasgupta, Papadimitriou, Vazirani. McGraw-Hill. 2006.

Given: A positive integer

Return: A sorted array

7 5 -2 4 7 8 -10 11

-10 -2 4 5 7 8 11

## Visualization

http://www.sorting-algorithms.com/quick-sort-3-way

## Running time

To prove an upper bound

$O(n\log n)$ on the expected running time of Quick Sort show that is satisfies the recurrence relation$$T(n) \le O(n)+\frac{1}{n}\sum_{i=1}^{n}(T(i)+T(n-i)).$$