Master Six Classic Sorting Algorithms in Python: From Bubble to Quick Sort

Sorting Algorithms

Sorting algorithms arrange items in an array from smallest to largest (or vice‑versa). The article assumes ascending order and illustrates each algorithm with animations (see GIFs) and Python code.

Bubble Sort

Bubble Sort repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order, causing larger elements to “bubble” to the end.

Python implementation:

<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

alist = [44, 46, 2, 26, 5, 4, 19, 36, 15, 3, 38, 27, 47]
bubbleSort(alist)  # => [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47]
</code>

Animation:

Selection Sort

Selection Sort repeatedly finds the minimum element from the unsorted portion and swaps it with the first unsorted element.

<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

alist = [44, 46, 2, 26, 5, 4, 19, 36, 15, 3, 38, 27, 47]
selectionSort(alist)  # => [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47]
</code>

Animation:

Insertion Sort

Insertion Sort builds a sorted sequence by inserting each unsorted element into its correct position within the already sorted part.

<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

alist = [44, 46, 2, 26, 5, 4, 19, 36, 15, 3, 38, 27, 47]
insertionSort(alist)  # => [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47]
</code>

Animation:

Shell Sort

Shell Sort is an improved version of Insertion Sort that sorts elements at a specific gap, gradually reducing the gap to 1.

<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

alist = [44, 46, 2, 26, 5, 4, 19, 36, 15, 3, 38, 27, 47]
shellSort(alist)  # => [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47]
</code>

Merge Sort

Merge Sort uses the divide‑and‑conquer strategy: it recursively splits the list, sorts each half, and merges the sorted halves.

<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
</code>

Quick Sort

Quick Sort selects a pivot, partitions the list into elements smaller and larger than the pivot, and recursively sorts the partitions.

<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]
</code>

Animation:

Python Built‑in Sorting

Python provides .sort() (list method) and sorted() (function). .sort() sorts the list in place, while sorted() returns a new sorted list and works on any iterable.

.sort() is a list method that modifies the list in place; sorted() can sort any iterable and returns a new list.

Examples:

<code>alist = [44, 46, 2, 26, 5, 4, 19, 36, 15, 3, 38, 27, 47]
alist.sort()  # alist becomes [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47]

alist.sort(reverse=True)  # descending order
</code>

Python’s sorting algorithm is Timsort, a hybrid of merge sort and insertion sort optimized for real‑world data.

Advanced usage of sorted() with key and reverse parameters allows sorting of complex structures such as lists of tuples or dictionaries.

<code>tuples = [('john', 3, 15), ('jane', 1, 12), ('dave', 2, 10), ('tom', 6, 11), ('kate', 5, 20)]
sorted(tuples, key=lambda x: x[1])  # sort by second element

dicts = {1:10, 2:70, 3:50, 4:100, 5:25}
sorted(dicts.items(), key=lambda x: x[0])  # sort by key
sorted(dicts.items(), key=lambda x: x[1])  # sort by value
</code>

References

hustcc https://github.com/hustcc/JS-Sorting-Algorithm

What are Sorting Algorithms? https://lamfo-unb.github.io/2019/04/21/Sorting-algorithms/

数据科学人工智能 经典排序算法和python详解（二）…

Python中sort()与sorted()区别 https://blog.csdn.net/u013759354/article/details/80243705

Tim sort, the fastest sort used in v8 and Python https://dev.to/jennieji/tim-sort-the-fastest-sort-used-in-v8-and-python-5e76