Sorting Algorithms

Bubble Sort

Definition: Bubble Sort is one of the simplest sorting algorithms. It works by repeatedly comparing adjacent elements and swapping them if they are in the wrong order. The process continues until no swaps are needed, meaning the list is sorted.

Step-by-Step Process

1. Compare the first two elements.
2. If the first element is greater, swap them.
3. Move to the next pair and repeat.
4. After one full pass, the largest element will be at the end.
5. Repeat the passes until the entire list is sorted.

Example

Input: [5, 3, 4, 1]

• Pass 1 → [3, 4, 1, 5]
• Pass 2 → [3, 1, 4, 5]
• Pass 3 → [1, 3, 4, 5]

Final Result: [1, 3, 4, 5]

Use Cases

• Sorting small datasets like 10 quiz scores.
• Teaching tool for understanding sorting logic.
• When simplicity is more important than speed.

Python 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]  # swap
    return arr

quiz_scores = [5, 3, 4, 1]
print("Bubble Sort result:", bubble_sort(quiz_scores))
        

Output: [1, 3, 4, 5]

Complexity: Best Case → O(n), Worst Case → O(n²), Space → O(1)

Selection Sort

Definition: Selection Sort scans the unsorted part, finds the smallest value, and places it at the next position in the sorted part. Fewer swaps. Many comparisons. Simple to reason about.

Step-by-Step Process

1. Start at index 0. Assume it holds the minimum.
2. Scan the rest of the array to find the true minimum.
3. Swap the minimum with the value at the current index.
4. Move to the next index and repeat until the array is sorted.

Example Walkthrough

Input: [29, 10, 14, 37, 13]

• i = 0 → min = 10 → swap with 29 → [10, 29, 14, 37, 13]
• i = 1 → min = 13 → swap with 29 → [10, 13, 14, 37, 29]
• i = 2 → min = 14 → already in place → [10, 13, 14, 37, 29]
• i = 3 → min = 29 → swap with 37 → [10, 13, 14, 29, 37]

Final Result: [10, 13, 14, 29, 37]

When should you use Selection Sort?

• When writes are expensive and you want fewer swaps.
• On small, fixed-size lists in embedded systems.
• When clarity matters more than speed.

Python Implementation

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_index = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        # Swap only once per outer loop
        arr[i], arr[min_index] = arr[min_index], arr[i]
    return arr

prices = [29, 10, 14, 37, 13]
print("Selection Sort result:", selection_sort(prices))
  

Expected output: [10, 13, 14, 29, 37]

Complexity: Best → O(n²), Average → O(n²), Worst → O(n²), Space → O(1), Stability → No

Insertion Sort

Definition: Insertion Sort builds the sorted list one item at a time. Each new element is compared with those already sorted and placed in the correct position. It’s like sorting a hand of playing cards — pick one card and insert it where it belongs.

Step-by-Step Process

1. Assume the first element is already sorted.
2. Pick the next element from the unsorted portion.
3. Compare it with elements in the sorted portion.
4. Shift larger elements one step to the right.
5. Insert the element into its correct position.
6. Repeat until the list is fully sorted.

Example Walkthrough

Input: [12, 11, 13, 5, 6]

• Take 11 → insert before 12 → [11, 12, 13, 5, 6]
• Take 13 → stays → [11, 12, 13, 5, 6]
• Take 5 → insert before 11 → [5, 11, 12, 13, 6]
• Take 6 → insert after 5 → [5, 6, 11, 12, 13]

Final Result: [5, 6, 11, 12, 13]

When should you use Insertion Sort?

• When the dataset is small (under 50 elements).
• When the dataset is already nearly sorted.
• When you want a simple, stable algorithm.

Python Implementation

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

attendance = [12, 11, 13, 5, 6]
print("Insertion Sort result:", insertion_sort(attendance))
  

Expected output: [5, 6, 11, 12, 13]

Complexity: Best → O(n), Average → O(n²), Worst → O(n²), Space → O(1), Stability → Yes

Merge Sort

Definition: Merge Sort is a classic divide-and-conquer algorithm. It divides the list into smaller parts, sorts each part, and then merges them back together in order. Unlike simpler sorts, it guarantees O(n log n) performance in every case.

Step-by-Step Process

1. Divide the list into two halves.
2. Recursively sort each half until only single elements remain.
3. Merge the sorted halves into one sorted list.

Example Walkthrough

Input: [38, 27, 43, 3, 9, 82, 10]

• Split → [38, 27, 43] and [3, 9, 82, 10]
• Split further → [38], [27, 43], [3, 9], [82, 10]
• Sort & merge → [27, 38, 43], [3, 9], [10, 82]
• Final merge → [3, 9, 10, 27, 38, 43, 82]

Final Result: [3, 9, 10, 27, 38, 43, 82]

When should you use Merge Sort?

• When working with very large datasets.
• When you need consistent performance regardless of input order.
• When you need a stable sorting algorithm (does not change the relative order of equal elements).
• For external sorting (e.g., data stored on disk instead of memory).

Python Implementation

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        L = arr[:mid]
        R = arr[mid:]

        merge_sort(L)
        merge_sort(R)

        i = j = k = 0
        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1

        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1

        while j < len(R):
            arr[k] = R[j]
            j += 1
            k += 1
    return arr

books = [38, 27, 43, 3, 9, 82, 10]
print("Merge Sort result:", merge_sort(books))
  

Expected output: [3, 9, 10, 27, 38, 43, 82]

Complexity: Best → O(n log n), Average → O(n log n), Worst → O(n log n), Space → O(n), Stability → Yes

Quick Sort

Definition: Quick Sort is another divide-and-conquer algorithm. It works by choosing a pivot, partitioning the list into two groups (elements smaller than the pivot and elements greater than the pivot), and then recursively sorting those groups. On average, it is one of the fastest sorting algorithms in practice.

Step-by-Step Process

1. Choose a pivot element (commonly the middle, first, or last element).
2. Partition the list into two sublists:
   • Left sublist → elements smaller than the pivot
   • Right sublist → elements greater than the pivot
3. Recursively apply Quick Sort to the left and right sublists.
4. Combine the results to form a fully sorted list.

Example Walkthrough

Input: [10, 7, 8, 9, 1, 5]

• Choose pivot = 9
• Left = [7, 8, 1, 5], Right = [10]
• Sort left recursively → [1, 5, 7, 8]
• Combine → [1, 5, 7, 8, 9, 10]

Final Result: [1, 5, 7, 8, 9, 10]

When should you use Quick Sort?

• When speed matters (average case is very fast).
• For in-memory sorting of large datasets.
• When extra memory usage should be minimal compared to Merge Sort.

Python Implementation

def quick_sort(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 quick_sort(left) + middle + quick_sort(right)

data = [10, 7, 8, 9, 1, 5]
print("Quick Sort result:", quick_sort(data))
  

Expected output: [1, 5, 7, 8, 9, 10]

Complexity: Best → O(n log n), Average → O(n log n), Worst → O(n²) (poor pivot choices), Space → O(log n), Stability → No

Heap Sort

Definition: Heap Sort is a comparison-based algorithm that uses a binary heap data structure. It repeatedly extracts the largest (or smallest) element from the heap and places it into the sorted list. It guarantees O(n log n) performance in all cases without requiring extra arrays like Merge Sort.

Step-by-Step Process

1. Build a max heap from the input data.
2. Swap the root (largest element) with the last element.
3. Reduce the heap size and heapify the root again.
4. Repeat until all elements are extracted and placed in sorted order.

Example Walkthrough

Input: [35, 12, 43, 8, 51]

• Build max heap → [51, 35, 43, 8, 12]
• Extract 51, re-heapify → [43, 35, 12, 8, 51]
• Extract 43, re-heapify → [35, 12, 8, 43, 51]
• Continue until → [8, 12, 35, 43, 51]

Final Result: [8, 12, 35, 43, 51]

When should you use Heap Sort?

• When consistent O(n log n) performance is required.
• When extra memory usage must be avoided (Heap Sort is in-place).
• For applications like leaderboards and scheduling tasks based on priority.

Python Implementation

def heapify(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2

    if left < n and arr[left] > arr[largest]:
        largest = left
    if right < n and arr[right] > arr[largest]:
        largest = right

    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def heap_sort(arr):
    n = len(arr)
    # Build max heap
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    # Extract elements one by one
    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]
        heapify(arr, i, 0)
    return arr

scores = [35, 12, 43, 8, 51]
print("Heap Sort result:", heap_sort(scores))
  

Expected output: [8, 12, 35, 43, 51]

Complexity: Best → O(n log n), Average → O(n log n), Worst → O(n log n), Space → O(1), Stability → No

Comparison of Sorting Algorithms

Lesson Wrap-Up

Sorting algorithms are more than academic exercises — they drive real-world systems from search engines to e-commerce platforms. The right choice depends on your dataset size, memory constraints, and whether stability matters.

For small or nearly sorted data, Insertion Sort is unbeatable. For very large datasets, Merge Sort provides consistency. For speed in practice, Quick Sort dominates. And for priority-based tasks, Heap Sort is the go-to solution.