Master Classic Sorting Algorithms in Python (Insertion to Radix)

Insertion Sort

The basic operation of insertion sort inserts an element into an already sorted list, producing a new sorted list. It is suitable for small data sets, has O(n^2) time complexity, and is stable.

def insert_sort(lists):
    count = len(lists)
    for i in range(1, count):
        key = lists[i]
        j = i - 1
        while j >= 0 and lists[j] > key:
            lists[j + 1] = lists[j]
            j -= 1
        lists[j + 1] = key
    return lists

Shell Sort

Shell sort is an improved version of insertion sort that uses decreasing gap intervals. It is not stable and was proposed by D.L. Shell in 1959.

def shell_sort(lists):
    count = len(lists)
    step = 2
    group = count // step
    while group > 0:
        for i in range(group):
            for j in range(i, count, group):
                key = lists[j]
                while j >= group and lists[j - group] > key:
                    lists[j] = lists[j - group]
                    j -= group
                lists[j] = key
        group //= step
    return lists

Bubble Sort

Bubble sort repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order, until no swaps are needed.

def bubble_sort(lists):
    count = len(lists)
    for i in range(count):
        for j in range(0, count - i - 1):
            if lists[j] > lists[j + 1]:
                lists[j], lists[j + 1] = lists[j + 1], lists[j]
    return lists

Quick Sort

Quick sort partitions the array around a pivot, recursively sorting the sub‑arrays. It uses divide‑and‑conquer and runs in O(n log n) on average.

def quick_sort(lists, left, right):
    if left >= right:
        return lists
    key = lists[left]
    low = left
    high = right
    while left < right and lists[right] >= key:
        right -= 1
    while left < right and lists[left] <= key:
        left += 1
    if left < right:
        lists[left], lists[right] = lists[right], lists[left]
    quick_sort(lists, low, left - 1)
    quick_sort(lists, left + 1, high)
    return lists

Selection Sort

Selection sort repeatedly selects the minimum element from the unsorted portion and swaps it with the first unsorted element.

def select_sort(lists):
    count = len(lists)
    for i in range(count):
        min_idx = i
        for j in range(i + 1, count):
            if lists[j] < lists[min_idx]:
                min_idx = j
        lists[i], lists[min_idx] = lists[min_idx], lists[i]
    return lists

Heap Sort

Heap sort builds a max‑heap from the list and repeatedly extracts the maximum element to produce a sorted array.

def adjust_heap(lists, i, size):
    lchild = 2 * i + 1
    rchild = 2 * i + 2
    max_idx = i
    if i < size // 2:
        if lchild < size and lists[lchild] > lists[max_idx]:
            max_idx = lchild
        if rchild < size and lists[rchild] > lists[max_idx]:
            max_idx = rchild
        if max_idx != i:
            lists[i], lists[max_idx] = lists[max_idx], lists[i]
            adjust_heap(lists, max_idx, size)

def build_heap(lists, size):
    for i in range((size // 2) - 1, -1, -1):
        adjust_heap(lists, i, size)

def heap_sort(lists):
    size = len(lists)
    build_heap(lists, size)
    for i in range(size - 1, -1, -1):
        lists[0], lists[i] = lists[i], lists[0]
        adjust_heap(lists, 0, i)
    return lists

Merge Sort

Merge sort recursively divides the list into halves, sorts each half, and merges them using a stable two‑way merge.

def merge(left, right):
    i = j = 0
    result = []
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

def merge_sort(lists):
    if len(lists) <= 1:
        return lists
    mid = len(lists) // 2
    left = merge_sort(lists[:mid])
    right = merge_sort(lists[mid:])
    return merge(left, right)

Radix Sort

Radix sort distributes elements into buckets according to digit positions, processing from least to most significant digit; it is stable and runs in O(n·k) time.

import math

def radix_sort(lists, radix=10):
    k = int(math.ceil(math.log(max(lists), radix)))
    for i in range(k):
        bucket = [[] for _ in range(radix)]
        for num in lists:
            bucket[(num // (radix ** i)) % radix].append(num)
        lists = [num for sublist in bucket for num in sublist]
    return lists