Sorting Algorithms Visualized

Interactive Visualizer

Python Implementations

Insertion Sort

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

Quick Sort (Median-of-Three Pivot)

def quick_sort(arr):
    def median_of_three(lo, hi):
        mid = (lo + hi) // 2
        triple = [(arr[lo], lo), (arr[mid], mid), (arr[hi], hi)]
        triple.sort(key=lambda x: x[0])
        return triple[1][1]

    def qs(lo, hi):
        if lo >= hi:
            return
        pivot_index = median_of_three(lo, hi)
        arr[pivot_index], arr[hi] = arr[hi], arr[pivot_index]
        pivot = arr[hi]
        i = lo
        for j in range(lo, hi):
            if arr[j] <= pivot:
                arr[i], arr[j] = arr[j], arr[i]
                i += 1
        arr[i], arr[hi] = arr[hi], arr[i]
        qs(lo, i - 1)
        qs(i + 1, hi)

    qs(0, len(arr) - 1)

Merge Sort

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        left = arr[:mid]
        right = arr[mid:]
        merge_sort(left)
        merge_sort(right)

        i = j = k = 0
        while i < len(left) and j < len(right):
            if left[i] <= right[j]:
                arr[k] = left[i]
                i += 1
            else:
                arr[k] = right[j]
                j += 1
            k += 1

        while i < len(left):
            arr[k] = left[i]
            i += 1
            k += 1
        while j < len(right):
            arr[k] = right[j]
            j += 1
            k += 1

Bucket (Counting) Sort

def counting_sort(arr):
    if not arr:
        return arr
    k = max(arr)  # assumes non-negative integers
    counts = [0] * (k + 1)
    for x in arr:
        counts[x] += 1
    i = 0
    for v, c in enumerate(counts):
        for _ in range(c):
            arr[i] = v
            i += 1

Time & Space Complexity

Stable means that if two elements have the same key or value, they keep the same relative order in the output as in the input.