Comprehensive Overview of Common Sorting Algorithms with Python Implementations

Sorting Algorithms Overview

Sorting algorithms are one of the most fundamental algorithms in data structures and algorithms.

They can be divided into internal sorting (data fits in memory) and external sorting (data too large for memory, requiring disk access). Common internal sorting algorithms include insertion sort, shell sort, selection sort, bubble sort, merge sort, quick sort, heap sort, counting sort, bucket sort, and radix sort.

Time Complexity

Quadratic O(n²) sorts: simple sorts such as direct insertion, direct selection, and bubble sort.

Linearithmic O(n log² n) sorts: quick sort, heap sort, and merge sort.

O(n^{1+ε}) sorts (ε between 0 and 1): shell sort.

Linear O(n) sorts: radix sort and bucket sort (also bucket and counting sorts).

Stability

Stability means that two equal keys retain their relative order after sorting.

Stable sorting algorithms: bubble sort, insertion sort, merge sort, and radix sort.

Unstable sorting algorithms: selection sort, quick sort, shell sort, and heap sort.

Terminology

n : data size.

k : number of buckets.

In‑place : uses constant extra memory.

Out‑place : uses additional memory.

1. Bubble Sort

Bubble sort repeatedly traverses the list, compares adjacent elements and swaps them if they are in the wrong order, causing larger elements to "bubble" to the end of the list.

Algorithm Steps

Compare adjacent elements; if the first is larger than the second, swap them.

Repeat the comparison from the first pair to the last pair; after this pass the largest element is at the end.

Repeat the whole process for the remaining unsorted portion.

Continue until no swaps are needed.

Python Code

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

2. Selection Sort

Selection sort repeatedly selects the smallest (or largest) element from the unsorted portion and moves it to the beginning (or end) of the sorted portion.

Algorithm Steps

Find the minimum (or maximum) element in the unsorted portion and swap it with the first unsorted element.

Repeat for the remaining unsorted portion until the entire list is sorted.

Python Code

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

3. Insertion Sort

Insertion sort builds a sorted sequence one element at a time by inserting each new element into its correct position within the already sorted part.

Algorithm Steps

Treat the first element as a sorted sub‑list.

Take the next element and insert it into the sorted sub‑list at the appropriate position, shifting larger elements to the right.

Repeat for all remaining elements.

Python Code

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

4. Shell Sort

Shell sort is an improved version of insertion sort that allows the exchange of items that are far apart by sorting elements at a specific gap and gradually reducing the gap.

Algorithm Steps

Choose a gap sequence t1, t2, …, tk where tk = 1.

Perform k passes of insertion sort using each gap.

When the gap is 1, the list is fully sorted.

Python Code

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

5. Merge Sort

Merge sort is a divide‑and‑conquer algorithm that recursively splits the list into halves, sorts each half, and merges the sorted halves.

Algorithm Steps

Recursively split the list into two halves until sub‑lists of size 1 are obtained.

Merge two sorted sub‑lists by repeatedly taking the smaller front element.

Continue merging until the whole list is sorted.

Python Code

def mergeSort(arr):
    import math
    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

6. Quick Sort

Quick sort selects a pivot element, partitions the list into elements less than the pivot and greater than the pivot, and recursively sorts the partitions.

Algorithm Steps

Choose a pivot element.

Reorder the list so that all elements less than the pivot come before it and all greater elements come after it.

Recursively apply quick sort to the sub‑lists on each side of the pivot.

Python Code

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]

7. Heap Sort

Heap sort builds a binary heap from the list and repeatedly extracts the maximum (or minimum) element to produce a sorted sequence.

Algorithm Steps

Build a max‑heap from the unsorted list.

Swap the first element (maximum) with the last element of the heap.

Reduce the heap size by one and heapify the root.

Repeat until the heap size is 1.

Python Code

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

8. Counting Sort

Counting sort counts the occurrences of each distinct value and then computes the positions of each value in the sorted output.

Python Code

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

9. Bucket Sort

Bucket sort distributes elements into a number of buckets, sorts each bucket individually (often using another sorting algorithm), and then concatenates the buckets.

Python Code

def bucket_sort(s):
    """Bucket sort"""
    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)
    return s

10. Radix Sort

Radix sort processes integer keys digit by digit, from least significant to most significant, using bucket distribution at each digit.

Python Code

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

For visual learners, the article also includes animated GIFs demonstrating each algorithm’s behavior.

At the end, promotional material invites readers to scan a QR code for a free Python public course and additional learning resources.