CQH103: Sorting Algorithms – Bubble Sort, QuickSort, and Merge Sort

Sorting is one of the most fundamental operations in programming. Whether you’re organizing numbers, names, or any kind of data, efficient sorting is crucial for performance. In this lesson, we’ll explore three key sorting algorithms: Bubble Sort, QuickSort, and Merge Sort—each with unique approaches and trade-offs.

Why Sorting Matters

Sorting is essential for many applications, from searching for data quickly to optimizing storage and display. It directly ties back to arrays and linked lists, the core data structures we covered in CQH102. The way data is structured impacts the efficiency of sorting, and choosing the right algorithm can make a huge difference in performance.

Bubble Sort – The Simple But Slow Approach

Bubble Sort repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. It continues until the list is fully sorted.

How It Works

  1. Compare the first two elements and swap if necessary.
  2. Move to the next pair and repeat.
  3. Continue until the largest element bubbles to the end.
  4. Repeat the process for the remaining elements.

Example in Python

# Bubble Sort Implementation
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]

numbers = [5, 3, 8, 4, 2]
bubble_sort(numbers)
print(numbers)  # Output: [2, 3, 4, 5, 8]

Performance

  • Time Complexity: O(n²) – very slow for large datasets.
  • Best For: Small datasets or when simplicity matters.

QuickSort – The Efficient Divide & Conquer Method

QuickSort is a divide and conquer algorithm that selects a pivot, partitions the array, and recursively sorts the subarrays.

How It Works

  1. Pick a pivot element.
  2. Partition the array so that elements smaller than the pivot go left, and larger ones go right.
  3. Recursively apply QuickSort to the left and right partitions.

Example in Python

# QuickSort Implementation
def quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quicksort(left) + middle + quicksort(right)

numbers = [5, 3, 8, 4, 2]
print(quicksort(numbers))  # Output: [2, 3, 4, 5, 8]

Performance

  • Time Complexity: O(n log n) on average.
  • Best For: Large datasets where speed matters.

Merge Sort – The Reliable and Stable Approach

Merge Sort also follows the divide and conquer strategy but ensures stability (preserving order of equal elements).

How It Works

  1. Divide the array into halves until each half contains a single element.
  2. Merge the halves back together in sorted order.

Example in Python

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

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:])
    result.extend(right[j:])
    return result

numbers = [5, 3, 8, 4, 2]
print(merge_sort(numbers))  # Output: [2, 3, 4, 5, 8]

Performance

  • Time Complexity: O(n log n), but requires extra space.
  • Best For: Sorting linked lists or when stability matters.

Choosing the Right Sorting Algorithm

Algorithm Best Case Average Case Worst Case Space Complexity Use Case
Bubble Sort O(n) O(n²) O(n²) O(1) Small datasets, simple needs
QuickSort O(n log n) O(n log n) O(n²) O(log n) Fast sorting, large datasets
Merge Sort O(n log n) O(n log n) O(n log n) O(n) Stable sorting, linked lists

Key Takeaways

  • Use Bubble Sort for simplicity or small datasets.
  • Use QuickSort for general-purpose fast sorting.
  • Use Merge Sort when stability is required or for linked lists.

Sorting is a foundational topic in computer science, and different sorting techniques work best for different data structures. Arrays work well with QuickSort due to fast random access, while linked lists benefit from Merge Sort’s stability.

Next Steps

Sorting is just the beginning! Next, we’ll dive into Searching Algorithms like Binary Search and Linear Search, showing how sorted data can make searching lightning-fast.

Want to try it yourself? Modify the above sorting algorithms to handle descending order sorting and post your solution in the comments! 🚀