Sorting Algorithms: Bubble, Merge, Quick Sort Compared with Python Code

Sorting Algorithms

Sorting is one of the most studied problems in computer science. Every developer should know how bubble, merge, and quick sort work and when to use each. They appear in every algorithm interview.

Bubble Sort — O(n²)

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:  # already sorted — early exit
            break
    return arr

# Trace: [64, 34, 25, 12, 22]
# Pass 1: [34, 25, 12, 22, 64]  ← 64 bubbles to end
# Pass 2: [25, 12, 22, 34, 64]
# Pass 3: [12, 22, 25, 34, 64]
print(bubble_sort([64, 34, 25, 12, 22]))  # [12,22,25,34,64]

Merge Sort — O(n log n) — Stable

def merge_sort(arr):
    if len(arr) <= 1:
        return arr  # base case

    mid   = len(arr) // 2
    left  = merge_sort(arr[:mid])   # divide
    right = merge_sort(arr[mid:])   # divide
    return merge(left, right)       # conquer

def merge(left, right):
    result = []
    i = j = 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:])   # remaining
    result.extend(right[j:])
    return result

arr = [38, 27, 43, 3, 9, 82, 10]
print(merge_sort(arr))  # [3, 9, 10, 27, 38, 43, 82]

Quick Sort — O(n log n) avg, O(n²) worst

def quick_sort(arr, low=0, high=None):
    if high is None: high = len(arr) - 1
    if low < high:
        pivot_idx = partition(arr, low, high)
        quick_sort(arr, low, pivot_idx - 1)   # left of pivot
        quick_sort(arr, pivot_idx + 1, high)  # right of pivot
    return arr

def partition(arr, low, high):
    pivot = arr[high]   # pick last element as pivot
    i     = low - 1     # index of smaller element

    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]

    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1  # pivot is now in correct position

arr = [10, 7, 8, 9, 1, 5]
print(quick_sort(arr))  # [1, 5, 7, 8, 9, 10]

Python Built-in Sort (Timsort)

# Python uses Timsort: O(n log n) — hybrid merge + insertion sort
arr = [3, 1, 4, 1, 5, 9, 2, 6]
arr.sort()           # in-place
sorted_arr = sorted(arr)  # returns new array

# Sort objects by key
users = [{'name':'Rahul','age':25},{'name':'Priya','age':22},{'name':'Amit','age':28}]
users.sort(key=lambda u: u['age'])          # ascending by age
users.sort(key=lambda u: u['age'], reverse=True)  # descending
users.sort(key=lambda u: (u['age'], u['name']))    # multi-key sort