Sorting algorithms/Quicksort: Difference between revisions

In this task, the goal is to sort an array (or list) of elements using the [http://en.wikipedia.org/wiki/Quicksort Quicksort] algorithm. The elements must have a total order and the index of the array can be of any discrete type. For languages where this is not possible, sort an array of integers. The algorithm goes like this (from the wiki):

function quicksort(array)

var list lessOrEqual, greater

if length(array) ≤ 1

return array

select a pivot value pivot from array

for each x in array

if x ≤ pivot then add x to lessOrEqual

if x > pivot then add x to greater

return concatenate(quicksort(lessOrEqual), quicksort(greater))

The "pivot" separates the dataset into two groups: those that are less than or equal to the value at the pivot and those that are greater than the pivot. The Quicksort's worst case time is O(n^2) for a completely sorted set, but otherwise it is O(n * log n). Its average time is slightly faster than that of the merge sort in most cases, even though they are both O(n * log n) sorts.