Comprehensive Overview of Common Sorting Algorithms with Python Implementations

Sorting algorithms are one of the most fundamental topics in data structures and algorithms. They can be divided into internal sorting , where data is sorted in memory, and external sorting , which handles data too large to fit into memory and requires disk access.

Common Internal Sorting Algorithms

Insertion sort, Shell sort, Selection sort, Bubble sort, Merge sort, Quick sort, Heap sort, Counting sort, Bucket sort, Radix sort, etc.

Time Complexity Overview

Quadratic (O(n²)) sorts: simple sorts like Insertion, Selection, Bubble.

Linearithmic (O(n log n)) sorts: Quick, Heap, Merge.

O(n^{1+ε}) sort: Shell sort.

Linear (O(n)) sorts: Counting, Bucket.

Stability

Stable sorts preserve the relative order of equal keys.

Stable algorithms: Bubble sort, Insertion sort, Merge sort, Counting sort.

Unstable algorithms: Selection sort, Quick sort, Shell sort, Heap sort.

Key Terminology

n : size of the data set.

k : number of buckets.

In‑place : uses only constant extra memory.

Out‑place : requires additional memory.

Algorithm Details and Python Implementations

1. Bubble Sort

Repeatedly compare adjacent elements and swap them if they are in the wrong order, bubbling the largest element to the end each pass.

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

2. Selection Sort

Find the minimum element in the unsorted portion and swap it with the first unsorted element.

<code>
<code>def selectionSort(arr):</code>
<code>    for i in range(len(arr) - 1):</code>
<code>        minIndex = i</code>
<code>        for j in range(i + 1, len(arr)):</code>
<code>            if arr[j] < arr[minIndex]:</code>
<code>                minIndex = j</code>
<code>        if i != minIndex:</code>
<code>            arr[i], arr[minIndex] = arr[minIndex], arr[i]</code>
<code>    return arr</code>
</code>

3. Insertion Sort

Build the sorted array one element at a time by inserting each new element into its correct position.

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

4. Shell Sort

An improved insertion sort that sorts elements far apart first using a decreasing gap sequence.

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

5. Merge Sort

A classic divide‑and‑conquer algorithm that recursively splits the array and merges sorted halves.

<code>
<code>def mergeSort(arr):</code>
<code>    if len(arr) < 2:</code>
<code>        return arr</code>
<code>    middle = len(arr) // 2</code>
<code>    left, right = arr[:middle], arr[middle:]</code>
<code>    return merge(mergeSort(left), mergeSort(right))</code>

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

6. Quick Sort

Uses a pivot to partition the array into elements smaller and larger than the pivot, then recursively sorts the partitions.

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

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

<code>def swap(arr, i, j):</code>
<code>    arr[i], arr[j] = arr[j], arr[i]</code>
</code>

7. Heap Sort

Builds a max‑heap from the array and repeatedly extracts the maximum element.

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

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

<code>def swap(arr, i, j):</code>
<code>    arr[i], arr[j] = arr[j], arr[i]</code>

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

8. Counting Sort

Counts occurrences of each integer value and reconstructs the sorted array; works only for integers within a known range.

<code>
<code>def countingSort(arr, maxValue):</code>
<code>    bucketLen = maxValue + 1</code>
<code>    bucket = [0] * bucketLen
<code>    for num in arr:</code>
<code>        bucket[num] += 1</code>
<code>    sortedIndex = 0</code>
<code>    for value, count in enumerate(bucket):</code>
<code>        while count > 0:</code>
<code>            arr[sortedIndex] = value</code>
<code>            sortedIndex += 1</code>
<code>            count -= 1</code>
<code>    return arr</code>
</code>

9. Bucket Sort

Distributes elements into a number of buckets, sorts each bucket (here using Python's built‑in sort), and concatenates the results.

<code>
<code>def bucket_sort(s):</code>
<code>    min_num = min(s)</code>
<code>    max_num = max(s)</code>
<code>    bucket_range = (max_num - min_num) / len(s)</code>
<code>    count_list = [[] for _ in range(len(s) + 1)]</code>
<code>    for i in s:</code>
<code>        count_list[int((i - min_num) // bucket_range)].append(i)</code>
<code>    s.clear()</code>
<code>    for bucket in count_list:</code>
<code>        for j in sorted(bucket):</code>
<code>            s.append(j)</code>
</code>

10. Radix Sort

Sorts numbers by processing individual digits from least significant to most significant using bucket (digit) distribution.

<code>
<code>def RadixSort(lst):</code>
<code>    i = 0</code>
<code>    n = 1</code>
<code>    max_num = max(lst)</code>
<code>    while max_num > 10 ** n:
<code>        n += 1</code>
<code>    while i < n:
<code>        bucket = {d: [] for d in range(10)}</code>
<code>        for x in lst:
<code>            radix = int((x / (10 ** i)) % 10)</code>
<code>            bucket[radix].append(x)</code>
<code>        j = 0
        for k in range(10):
            for y in bucket[k]:
                lst[j] = y
                j += 1
        i += 1
<code>    return lst</code>
</code>

Performance Tips

Bucket sort is fastest when input data can be evenly distributed across many buckets, and slowest when all elements fall into a single bucket.

Reference: Original source