Sorting algorithms

Organizing data allows us to find things faster, but there is no one-size-fits-all approach.

The idea

Sorting is one of the most studied problems in computer science. Comparison sorts (like Merge, Quick, and Heap sort) operate by asking "is A bigger than B?". The mathematical limit for this is O(n log n) time.

On the other hand, Non-comparison sorts (like Counting or Radix sort) bypass this limit by exploiting the actual values of the data (like grouping numbers into buckets by their digits), achieving O(n) time, but with strict restrictions on the type of data they can handle.

Select an algorithm and press Play.

How it works

A classic, stable O(n²) comparison sort is Insertion Sort. While slow for large datasets, it is extremely fast for small or nearly sorted arrays.

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        
        # Shift elements greater than key to the right
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
            
        # Place key in its correct position
        arr[j + 1] = key
        
    return arr

Cost

Time Complexity O(N log N) typical

Space Complexity O(1) or O(N)

Merge Sort is O(n log n) time and O(n) space. Quick Sort is typically O(n log n) time and O(log n) space. Heap Sort is O(n log n) time and O(1) space.

Watch out for

Stability: A "stable" sort preserves the relative order of equal elements. If you sort a list of people by Age, and then sort by Name, a stable sort keeps people with the same name ordered by their age. (Merge sort is stable; Quick sort is not).
Worst-case Quick Sort: If you pick a bad pivot (like always picking the last element in an already sorted array), Quick Sort degrades to O(n²).