QuickSort

Algorithm

• Pick a pivot from the list.
• Reorder the list so that all the elements with values less than the pivot are arranged before the pivot and all the other elements are arranged after the pivot. Numbers equal to the pivot can go in either partitions. At this point, the pivot is in its final position.
• Recursively apply the above steps to the left partition and to the right partition.

Performance

• Worst case:
• Best case:
• Average case:
• Space complexity: auxiliary or auxiliary

Implementations

• LSL
• Ruby (sorts array a in relative order of b)
• C
• ARexx
• C#