Classification and Implementation of Common Sorting Algorithms in Python

Sorting Algorithm Classification

Sorting algorithms can be divided into four main categories:

Internal sorting : All elements are stored in memory during sorting. Common internal algorithms include Bubble Sort, Selection Sort, Insertion Sort, Shell Sort, Merge Sort, Quick Sort, Heap Sort, Counting Sort, Bucket Sort, and Radix Sort.

External sorting : Elements cannot be fully loaded into memory and must be moved between memory and external storage during the sort.

Comparison‑based sorting : Order is determined by comparing elements; the theoretical lower bound is O(n log n).

Non‑comparison sorting : Order is determined without direct comparisons, allowing linear‑time sorts such as Counting Sort, Bucket Sort, and Radix Sort.

In practice, internal sorting algorithms perform two basic operations—comparison and movement. Not all internal sorts rely on comparisons, and each algorithm has its own advantages and disadvantages, making it hard to declare a single best algorithm.

Stability : A sort is stable if equal keys retain their original relative order after sorting.

Typical time‑complexity comparisons are shown in the following figure:

1. Bubble Sort (Bubble Sort)

1.1 Principle

Repeatedly traverse the list, compare adjacent elements, and swap them if they are in the wrong order. Each pass moves the largest unsorted element to its final position at the end of the list.

1.2 Steps

① Compare adjacent elements and swap if the first is larger. ② Continue this process for each pair from the start to the end. ③ Repeat steps ① and ② for the whole list until no swaps are needed.

1.3 Code Implementation

<code>def bubbleSort(arr):</code>
<code>    for i in range(len(arr)-1):  # each pass</code>
<code>        for j in range(len(arr)-i-1):  # compare adjacent items</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>

1.4 Optimized Version (flag)

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

1.5 Example Output

<code># Unoptimized output (each pass printed)</code>
<code>[3, 38, 5, 44, 15, 36, 26, 27, 2, 46, 4, 19, 47, 48, 50]</code>
<code># ... (subsequent passes omitted for brevity)</code>
<code># Optimized output</code>
<code>[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]</code>

2. Selection Sort (Selection Sort)

2.1 Principle

Repeatedly select the smallest (or largest) element from the unsorted portion and swap it with the first unsorted element. This algorithm is unstable.

2.2 Steps

① Find the minimum element in the unsorted part and place it at the beginning. ② Repeat for the remaining unsorted portion until the list is sorted.

2.3 Code Implementation

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

2.4 Example Output

<code># After each pass the list is printed</code>
<code>[2, 44, 38, 5, 47, 15, 36, 26, 27, 3, 46, 4, 19, 50, 48]</code>
<code># ... (subsequent passes omitted)</code>
<code>[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 44, 46, 47, 48, 50]</code>

3. Insertion Sort (Insertion Sort)

3.1 Principle

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

3.2 Steps

① Assume the first element is sorted. ② Take the next element and scan the sorted portion from right to left. ③ Shift larger elements to the right until the correct position is found. ④ Insert the new element. ⑤ Repeat for all elements.

3.3 Code Implementation

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

3.4 Example Output

<code># Starting list</code>
<code>[0, 9, 8, 7, 1, 2, 3, 4, 5, 6]</code>
<code># After each insertion pass</code>
<code>[0, 8, 9, 7, 1, 2, 3, 4, 5, 6]</code>
<code>[0, 7, 8, 9, 1, 2, 3, 4, 5, 6]</code>
<code>...</code>
<code>[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]</code>

4. Shell Sort (Shell Sort)

4.1 Principle

Shell Sort is an improved version of Insertion Sort that sorts elements at a specific gap, gradually reducing the gap until it becomes 1, at which point the list is fully sorted.

4.2 Steps

① Choose an initial gap d = n/2. ② Perform insertion sort on sub‑arrays formed by elements d apart. ③ Reduce the gap (d //= 2) and repeat until d = 1.

4.3 Code Implementation

<code>def insertion_sort_gap(arr, gap):</code>
<code>    for i in range(gap, len(arr)):</code>
<code>        tmp = arr[i]
<code>        j = i - gap
<code>        while j >= 0 and arr[j] > tmp:
<code>            arr[j + gap] = arr[j]
<code>            j -= gap
<code>        arr[j + gap] = tmp

<code>def shell_sort(arr):</code>
<code>    d = len(arr) // 2
<code>    while d >= 1:
<code>        insertion_sort_gap(arr, d)
<code>        d //= 2
<code>    return arr</code>

4.4 Example Output

<code># After each gap reduction the list is printed</code>
<code>[3, 1, 2, 6, 5, 7, 4, 9, 8]</code>
<code>[2, 1, 3, 6, 4, 7, 5, 9, 8]</code>
<code>[1, 2, 3, 4, 5, 6, 7, 8, 9]</code>

5. Merge Sort (Merge Sort)

5.1 Principle

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

5.2 Steps

① Split the list until each sub‑list contains a single element. ② Merge pairs of sorted sub‑lists into larger sorted lists until the whole list is merged.

5.3 Code Implementation

<code>def merge(arr, low, mid, high):</code>
<code>    i, j = low, mid + 1
<code>    ltmp = []
<code>    while i <= mid and j <= high:
<code>        if arr[i] < arr[j]:
<code>            ltmp.append(arr[i]); i += 1
<code>        else:
<code>            ltmp.append(arr[j]); j += 1
<code>    while i <= mid:
<code>        ltmp.append(arr[i]); i += 1
<code>    while j <= high:
<code>        ltmp.append(arr[j]); j += 1
<code>    arr[low:high+1] = ltmp

<code>def merge_sort(arr, low, high):</code>
<code>    if low < high:
<code>        mid = (low + high) // 2
<code>        merge_sort(arr, low, mid)
<code>        merge_sort(arr, mid+1, high)
<code>        merge(arr, low, mid, high)
<code>        print(arr)  # print after each merge
<code>    return arr

5.4 Example Output

<code>[1, 7, 3, 2, 6, 9, 4]</code>
<code>[1, 2, 3, 7, 6, 9, 4]</code>
<code>[1, 2, 3, 4, 6, 7, 9]</code>

6. Quick Sort (Quick Sort)

6.1 Principle

Quick Sort selects a pivot, partitions the list into elements less than the pivot and elements greater than the pivot, and then recursively sorts the partitions. It is one of the fastest general‑purpose sorting algorithms.

6.2 Steps

① Choose a pivot element. ② Rearrange the list so that elements smaller than the pivot are on the left and larger elements are on the right. ③ Recursively apply the same process to the left and right sub‑lists.

6.3 Code Implementation

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

<code>def quick_sort(arr, left, right):</code>
<code>    if left < right:
<code>        mid = partition(arr, left, right)
<code>        quick_sort(arr, left, mid-1)
<code>        quick_sort(arr, mid+1, right)
<code>    return arr

6.4 Example Output

<code>[2, 1, 4, 3, 5, 6, 7, 9, 8]</code>
<code>[1, 2, 4, 3, 5, 6, 7, 9, 8]</code>
<code>[1, 2, 3, 4, 5, 6, 7, 9, 8]</code>
<code>[1, 2, 3, 4, 5, 6, 7, 8, 9]</code>

7. Heap Sort (Heap Sort)

7.1 Principle

Heap Sort uses a binary heap data structure (usually a max‑heap) to repeatedly extract the maximum element and rebuild the heap, resulting in a sorted array.

7.2 Steps

① Build a heap from the unsorted array. ② Swap the heap's root (maximum) with the last element. ③ Reduce the heap size and heapify the new root. ④ Repeat until the heap is empty.

7.3 Code Implementation

<code>def sift(arr, low, high):</code>
<code>    i = low
<code>    j = 2 * i + 1
<code>    tmp = arr[low]
<code>    while j <= high:
<code>        if j + 1 <= high and arr[j+1] > arr[j]:
<code>            j = j + 1
<code>        if arr[j] > tmp:
<code>            arr[i] = arr[j]
<code>            i = j
<code>            j = 2 * i + 1
<code>        else:
<code>            arr[i] = tmp
<code>            break
<code>    else:
<code>        arr[i] = tmp

<code>def heap_sort(arr):</code>
<code>    n = len(arr)
<code>    for i in range((n-2)//2, -1, -1):
<code>        sift(arr, i, n-1)
<code>    for i in range(n-1, -1, -1):
<code>        arr[0], arr[i] = arr[i], arr[0]
<code>        sift(arr, 0, i-1)
<code>    return arr

7.4 Example Output

<code># Building heap</code>
<code>[2, 7, 26, 25, 19, 17, 1, 90, 3, 36]</code>
<code># After heap sort</code>
<code>[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]</code>

8. Counting Sort (Counting Sort)

8.1 Principle

Counting Sort counts the occurrences of each distinct integer within a known range and then reconstructs the sorted list based on those counts. It runs in O(n + k) time, where k is the range of input values.

8.2 Code Implementation

<code>def count_sort(arr):</code>
<code>    if len(arr) < 2:
<code>        return arr
<code>    max_num = max(arr)
<code>    count = [0 for _ in range(max_num + 1)]
<code>    for val in arr:
<code>        count[val] += 1
<code>    arr.clear()
<code>    for ind, val in enumerate(count):
<code>        for _ in range(val):
<code>            arr.append(ind)
<code>    return arr

8.3 Example Output

<code>[1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3, 4, 4, 6, 7, 7, 8, 8, 9, 9]</code>

9. Bucket Sort (Bucket Sort)

9.1 Principle

Bucket Sort distributes elements into a fixed number of buckets based on a mapping function, sorts each bucket individually (often with another sorting algorithm), and then concatenates the buckets.

9.2 Code Implementation

<code>def bucket_sort(arr):</code>
<code>    max_num = max(arr)
<code>    n = len(arr)
<code>    buckets = [[] for _ in range(n)]
<code>    for var in arr:
<code>        i = min(var // (max_num // n), n-1)
<code>        buckets[i].append(var)
<code>        # Keep bucket sorted (insertion sort style)
<code>        for j in range(len(buckets[i])-1, 0, -1):
<code>            if buckets[i][j] < buckets[i][j-1]:
<code>                buckets[i][j], buckets[i][j-1] = buckets[i][j-1], buckets[i][j]
<code>            else:
<code>                break
<code>    sorted_arr = []
<code>    for buc in buckets:
<code>        sorted_arr.extend(buc)
<code>    return sorted_arr

9.3 Example Output

<code>[2, 7, 8, 12, 17, 19, 22, 23, 26, 33, 35, 39, 42, 42, 56]</code>

10. Radix Sort (Radix Sort)

10.1 Principle

Radix Sort processes integer keys digit by digit, from least significant to most significant, using a stable counting sort (or bucket sort) at each digit.

10.2 Code Implementation

<code>def radix_sort(li):</code>
<code>    max_num = max(li)
<code>    it = 0
<code>    while 10 ** it <= max_num:
<code>        buckets = [[] for _ in range(10)]
<code>        for var in li:
<code>            digit = (var // 10 ** it) % 10
<code>            buckets[digit].append(var)
<code>        li.clear()
<code>        for buc in buckets:
<code>            li.extend(buc)
<code>        it += 1
<code>    return li

10.3 Example Output

<code>[1, 7, 10, 82, 577, 743, 2030, 2599, 3138, 3221, 4127, 4793, 5622, 9420, 9680]</code>

Additional Resources

Scan the QR code below to receive a free Python tutorial series and a collection of hundreds of gigabytes of learning materials, including e‑books, projects, source code, and more.

Click "Read Original" for the full article.