Quick Sort

Quick Sort is a highly efficient divide-and-conquer sorting algorithm. It works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively.

Quick Sort is often faster in practice than other O(n log n) algorithms due to its cache efficiency and in-place sorting. However, its worst-case time complexity is O(n²), which occurs when the smallest or largest element is always chosen as the pivot.

With good pivot selection (such as using the median or randomization), Quick Sort is one of the fastest sorting algorithms for large datasets.

Time Complexity

CaseTime Complexity
BestO(n log n)
AverageO(n log n)
WorstO(n²)

Code Examples

# Python - quick sort
def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)