Sorting Algorithms — Bubble, Selection, Merge

After completing this topic

You will be able to explain how three sorting algorithms work, and compare their time complexities, advantages, and disadvantages.

Why learn sorting?

Sorting is one of the most basic and most studied problems in programming. While you rarely implement sorting algorithms directly in practice (just use Python's sorted()), studying sorting algorithms trains your algorithmic thinking — how to break down a problem, iterate, and optimize.

Bubble Sort — Most intuitive

Compare two adjacent elements, and swap them if they are in the wrong order. Repeat this until the entire list is sorted.

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

# [5, 3, 8, 1, 2] → [3, 5, 1, 2, 8] → ... → [1, 2, 3, 5, 8]

Working process (one pass):

[5, 3, 8, 1, 2]
 5>3 → swap → [3, 5, 8, 1, 2]
 5<8 → keep → [3, 5, 8, 1, 2]
 8>1 → swap → [3, 5, 1, 8, 2]
 8>2 → swap → [3, 5, 1, 2, 8]  ← 8 moves to the end

The larger values "bubble up" like bubbles, hence the name. Time complexity: O(n²). Easy to understand but slow.

Selection Sort — Pick the smallest and put it at the front

Find the smallest value in the entire list and move it to the front. Then, find the smallest value in the remaining list and move it to the second position. Repeat this.

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

Working process:

[5, 3, 8, 1, 2]
 min=1 → [1, 3, 8, 5, 2]
 min=2 → [1, 2, 8, 5, 3]
 min=3 → [1, 2, 3, 5, 8]
 done

Time complexity: O(n²). The same as bubble sort, but with fewer swaps, so it is slightly faster in practice.

Merge Sort — Divide and conquer

Idea: Divide the list in half, sort each half, and then merge them.

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])   # Sort the left half
    right = merge_sort(arr[mid:])  # Sort the right half
    
    return merge(left, right)

def merge(left, right):
    result = []
    i, j = 0, 0
    
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    
    result.extend(left[i:])
    result.extend(right[j:])
    return result

Working process:

[5, 3, 8, 1, 2]
    ↙         ↘
[5, 3, 8]   [1, 2]
  ↙   ↘       ↓
[5] [3,8]  [1, 2]
     ↓       ↓
[5] [3,8] [1,2]
  ↘  ↙      ↓
[3,5,8]  [1,2]
    ↘     ↙
[1, 2, 3, 5, 8]

Time complexity: O(n log n). It divides in half each time (log n steps) × compares n times in each step = O(n log n). This is the theoretical optimal for comparison-based sorting.

Performance comparison

• Stable: The original order of elements with the same value is preserved. (e.g., the order of students with the same score)
• Bubble/Selection does not require extra memory (in-place), but Merge requires creating a new list.

With 10,000 elements: Bubble/Selection ≈ 100 million operations, Merge ≈ 130,000 operations. A difference of 770 times.

How is it used in practice?

# Python built-in — Timsort (hybrid of Merge and Insertion Sort)
numbers = [5, 3, 8, 1, 2]
sorted(numbers)           # Returns a new list
numbers.sort()             # Sorts the original list

# Specify a key
students = [("Kim Hoon", 90), ("Lee Soo", 85), ("Park Jin", 95)]
sorted(students, key=lambda s: s[1])  # Sort by score
sorted(students, key=lambda s: s[1], reverse=True)  # Descending order

Python's sorted() uses the Timsort algorithm. It combines the advantages of merge sort and insertion sort, and is very efficient for real-world data. This is why you don't need to implement sorting yourself.

Key takeaways

The three algorithms solve the same problem with different approaches, and this difference manifests as a dramatic performance difference of O(n²) vs. O(n log n). This is why we study algorithms — even if they produce the same result, how you achieve it can make a difference of 1000 times or more. The same principle applies to all algorithm problems, not just sorting, but also searching, graphs, and optimization.