QuickSort

Divide and Conquer. Little non-trivial.

1. Pick a Pivot Element (some element in the array)

2. Divide the array into two, left and right. Left would be all less than pivot and right will be all greater than this pivot.

3. Keep dividing the array (recursively) till you have two elements.e.g in the half pick another (any) pivot element and divide it further into 2.

4. Sort last two elements. The left and right would be sorted. Thus merging step is trivial.

Complexity: n² to nlogn, depending on Pivot Element. If pivot is smallest(or largest) element, complexity is n². If it is middle element (meaning the array is divided into equal halves, always), it would be nlogn.

Benifits:

1. Complexity is generally lesser than n2

2. In-place sorting

References:

1. http://en.wikipedia.org/wiki/Quicksort