quicksort

The quicksort algorithm:
- Select a pivot from the list.
- Reorder the list so that all the elements lesser than pivot lie before it and all elements greater than pivot lie after it. This is partition operation based on the pivot using the divide and conquer strategy.
- Recurse on the lesser and greater lists.

Depending upon the pivot selection method, the partition condition can be adjusted so that this version of quicksort is a stable sort. However, it is not in-place as it requires Ω(n) extra space.

quicksort(List array):
    if array.size() <= 1:
       return array 
    pivot = array[0]
    for i = 0 to n:
       if array[i] < pivot:
          append to list lesser
       else
          append to list greater 
    return concatenate(quicksort(lesser), pivot, quicksort(greater))

The below version of quicksort is in-place. It has a tweaked partition method which temporarily moves he pivot to the end of the sub-list, partitions the sub-list, moves the pivot to its final position (storePivotIndex).

quicksort(List array):
    if array.size() <= 1:
       return array 
    pivot = array[0]
    for i = 0 to n:
       if array[i] < pivot:
          append to list lesser
       else
          append to list greater 
    return concatenate(quicksort(lesser), pivot, quicksort(greater))
quicksort(List array, left, right):
    if right <= left: return
    //select pivotIndex, pivot
    pivotFinalIndex = partition(array, left, right, pivotIndex)
    quicksort(array, left, pivotFinalIndex-1)
    quicksort(array, pivotFinalIndex+1, right)


quicksort_wrapper(List array):
    quicksort(array, 0, array.length())


// returns final index of the selected pivot
int partition(List array, left, right, pivotIndex):
    //after partition, storePivotIndex's value is the final index for the pivot
    storePivotIndex = left 
    //pivot to end of sub-list
    swap (array[pivotIndex], array[right]) 
    for i = left to right-1 :
       if (array[i] < pivot):
          swap(array[i], array[storePivotIndex])
          storePivotIndex++
    //pivot to its final position 
    swap (array[storePivotIndex], array[right]) 
    return storePivotIndex

Efficiency of quicksort is O(nlogn) on average but O(n^2) in worst case. Quicksort runs faster than other O(nlogn) sorting algorithms on arrays due to the 'principle of locality' nature of its inner loop.

The selection of good pivot is critical for its efficiency. The chances of always selecting poor pivot are low which results in O(n^2) time. The best pivot is the median of the list which if always selected would result in logn calls and O(nlogn) time. Even if the list is divided into 1/4 and 3/4 parts for all calls, it would result in 4x logn calls i.e. still O(nlogn) time. Thus on average, it requires O(nlogn) time.

For in-place partitioning version of quicksort, the space required is O(1) (neglecting recursion overhead).