Sorting Algorithms Overview with Python Implementations

Sorting algorithms are a fundamental topic in computer science, divided into internal sorting (operating on data in memory) and external sorting (handling data too large for memory). Common internal sorting methods include bubble sort, selection sort, insertion sort, shell sort, merge sort, quick sort, heap sort, counting sort, bucket sort, and radix sort.

Bubble Sort

A simple, stable algorithm that repeatedly swaps adjacent out‑of‑order elements until the list is sorted.

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

Selection Sort

An unstable O(n²) algorithm that repeatedly selects the minimum element from the unsorted portion and swaps it into place.

def selectionSort(arr):
    for i in range(len(arr)-1):
        # record index of smallest element
        minIndex = i
        for j in range(i+1, len(arr)):
            if arr[j] < arr[minIndex]:
                minIndex = j
        # swap if a smaller element was found
        if i != minIndex:
            arr[i], arr[minIndex] = arr[minIndex], arr[i]
    return arr

Insertion Sort

A stable algorithm that builds the sorted array one element at a time by inserting each new element into its correct position.

def insertionSort(arr):
    for i in range(len(arr)):
        preIndex = i-1
        current = arr[i]
        while preIndex >= 0 and arr[preIndex] > current:
            arr[preIndex+1] = arr[preIndex]
            preIndex -= 1
        arr[preIndex+1] = current
    return arr

Shell Sort

An improved insertion sort that uses a diminishing gap sequence to partially sort the list before a final insertion pass.

def shellSort(arr):
    import math
    gap = 1
    while gap < len(arr)/3:
        gap = gap*3 + 1
    while gap > 0:
        for i in range(gap, len(arr)):
            temp = arr[i]
            j = i - gap
            while j >= 0 and arr[j] > temp:
                arr[j+gap] = arr[j]
                j -= gap
            arr[j+gap] = temp
        gap = math.floor(gap/3)
    return arr

Merge Sort

A stable O(n log n) divide‑and‑conquer algorithm that recursively splits the list and merges sorted sub‑lists.

def mergeSort(arr):
    if len(arr) < 2:
        return arr
    middle = math.floor(len(arr)/2)
    left, right = arr[0:middle], arr[middle:]
    return merge(mergeSort(left), mergeSort(right))

def merge(left, right):
    result = []
    while left and right:
        if left[0] <= right[0]:
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))
    while left:
        result.append(left.pop(0))
    while right:
        result.append(right.pop(0))
    return result

Quick Sort

An efficient average‑case O(n log n) algorithm that selects a pivot, partitions the list, and recursively sorts the partitions.

def quickSort(arr, left=None, right=None):
    left = 0 if not isinstance(left, (int, float)) else left
    right = len(arr)-1 if not isinstance(right, (int, float)) else right
    if left < right:
        partitionIndex = partition(arr, left, right)
        quickSort(arr, left, partitionIndex-1)
        quickSort(arr, partitionIndex+1, right)
    return arr

def partition(arr, left, right):
    pivot = left
    index = pivot + 1
    i = index
    while i <= right:
        if arr[i] < arr[pivot]:
            swap(arr, i, index)
            index += 1
        i += 1
    swap(arr, pivot, index-1)
    return index-1

def swap(arr, i, j):
    arr[i], arr[j] = arr[j], arr[i]

Heap Sort

An O(n log n) comparison‑based sort that builds a max‑heap and repeatedly extracts the maximum element.

def buildMaxHeap(arr):
    import math
    for i in range(math.floor(len(arr)/2), -1, -1):
        heapify(arr, i)

def heapify(arr, i):
    left = 2*i + 1
    right = 2*i + 2
    largest = i
    if left < arrLen and arr[left] > arr[largest]:
        largest = left
    if right < arrLen and arr[right] > arr[largest]:
        largest = right
    if largest != i:
        swap(arr, i, largest)
        heapify(arr, largest)

def swap(arr, i, j):
    arr[i], arr[j] = arr[j], arr[i]

def heapSort(arr):
    global arrLen
    arrLen = len(arr)
    buildMaxHeap(arr)
    for i in range(len(arr)-1, 0, -1):
        swap(arr, 0, i)
        arrLen -= 1
        heapify(arr, 0)
    return arr

Counting Sort

A linear‑time non‑comparison sort for integers within a known range, using a frequency array.

def countingSort(arr, maxValue):
    bucketLen = maxValue + 1
    bucket = [0] * bucketLen
    sortedIndex = 0
    arrLen = len(arr)
    for i in range(arrLen):
        bucket[arr[i]] += 1
    for j in range(bucketLen):
        while bucket[j] > 0:
            arr[sortedIndex] = j
            sortedIndex += 1
            bucket[j] -= 1
    return arr

Bucket Sort

An extension of counting sort that distributes elements into a number of buckets, each of which is sorted individually.

def bucket_sort(s):
    """桶排序"""
    min_num = min(s)
    max_num = max(s)
    bucket_range = (max_num - min_num) / len(s)
    count_list = [[] for i in range(len(s) + 1)]
    for i in s:
        count_list[int((i - min_num)//bucket_range)].append(i)
    s.clear()
    for i in count_list:
        for j in sorted(i):
            s.append(j)

Radix Sort

A non‑comparison sort that processes integer digits (or characters) from least to most significant using bucket queues.

def RadixSort(list):
    i = 0  # start with least‑significant digit
    n = 1
    max_num = max(list)
    while max_num > 10**n:
        n += 1
    while i < n:
        bucket = {}
        for x in range(10):
            bucket.setdefault(x, [])
        for x in list:
            radix = int((x / (10**i)) % 10)
            bucket[radix].append(x)
        j = 0
        for k in range(10):
            if len(bucket[k]) != 0:
                for y in bucket[k]:
                    list[j] = y
                    j += 1
        i += 1
    return list

Each algorithm is accompanied by its time‑complexity analysis (e.g., O(n²) for simple sorts, O(n log n) for merge, quick, and heap sorts) and a discussion of stability, which determines whether equal keys preserve their original order after sorting.