Quicksort stands out due to its elegance, speed, and practical performance. It is widely used in real-world systems, including standard libraries of many programming languages. It is based on the divide-and-conquer paradigm.

How it works

But how it works? Pick a pivot, an element from the list. Usually, we pick the element in the middle of the list. Partition the list to three different lists. One list with elements less than the pivot, one with elements equal to the pivot and one with elements greater than the pivot. Recursively sort sort the less than and greater than lists. Finally, combine the results and you have a sorted list.

What makes quick sort so great is the low memory overhead, since it uses in place partitioning. The time complexity can vary from O(n²) in the worst case scenario and O(n log n) in the best and average case scenario.

Example

def quicksort(arr):
    if len(arr) <= 1:
        return arr

    pivot = arr[len(arr) // 2]  # choose middle element as pivot

    less = [x for x in arr if x < pivot]
    equal = [x for x in arr if x == pivot]
    greater = [x for x in arr if x > pivot]

    return quicksort(less) + equal + quicksort(greater)