Quick sort is a divide and conquer sorting algorithm that was invented by Tony Hoare in 1959. It has an average case time complexity of O(n*log(n)), which makes it more efficient than merge sort on average.
Like merge sort, quick sort works by dividing the input array into two halves and sorting each half recursively. However, it has a slightly different way of dividing the array.
Here’s the basic outline of the algorithm:
1) If the input array has a length of 0 or 1, then it is already sorted, so return it.
2) Pick a pivot element from the array.
3) Divide the array into two halves: one containing elements less than the pivot, and the other containing elements greater than or equal to the pivot.
4) Recursively sort the two halves.
5) Concatenate the sorted halves and the pivot element, in that order.
function quick_sort(array): if length of array <= 1: return array pivot = some element of array left = elements of array that are < pivot right = elements of array that are >= pivot return quick_sort(left) + pivot + quick_sort(right)