Welcome to the World of Sorting Algorithms!

Hello future Computer Scientists! This chapter is all about sorting—one of the most fundamental and important concepts in computing. An algorithm is simply a set of clear, step-by-step instructions designed to solve a problem.

What will you learn? You will learn the two key sorting algorithms required by your specification: Bubble sort and Merge sort. You will explore how they work step-by-step and compare their relative advantages and disadvantages.

Why is this important? Imagine trying to find a specific word in a dictionary where the words were placed randomly, or searching for a contact on your phone list that was not alphabetised! Sorting makes searching fast and efficient. When data is sorted, computers can locate information far more quickly.

I. The Core Concept: What is a Sorting Algorithm?

The Goal of Sorting

A sorting algorithm is a process that takes an input list of items and rearranges them so that they are in a specific order (either ascending, like 1, 2, 3, or descending, like Z, Y, X).

  • Input: A collection of unsorted items (e.g., [5, 2, 8, 1]).
  • Process: The sorting algorithm applies comparison, swapping, or splitting/merging rules.
  • Output: The sorted collection (e.g., [1, 2, 5, 8]).

Prerequisite Concept: Swapping

Algorithms like Bubble sort rely on swapping items. Swapping means exchanging the positions of two elements in a list.
Example: If List[A] = 5 and List[B] = 2, after swapping, List[A] = 2 and List[B] = 5.

II. Bubble Sort

Bubble Sort is one of the simplest sorting algorithms to understand and implement.

Analogy: Bubbles Rising

Imagine you have a glass of fizzy water where bubbles rise to the surface. In Bubble Sort, the largest elements gradually "bubble up" to the end of the list over repeated passes.

How Bubble Sort Works (Step-by-Step)

Bubble Sort repeatedly passes through the list, compares adjacent (side-by-side) elements, and swaps them if they are in the wrong order.

Process Breakdown:
  1. Start at the beginning of the list.
  2. Compare the first item with the second item.
  3. If they are out of order, swap them.
  4. Move to the next adjacent pair (second and third item), compare, and swap if needed.
  5. Continue this process until you reach the end of the list. This completes one pass.
  6. After the first pass, the largest item is guaranteed to be in its correct, final position at the end of the list.
  7. Repeat the process for subsequent passes (Pass 2, Pass 3, etc.).
  8. The algorithm stops when a complete pass is made with zero swaps, showing that the list is fully sorted.
Quick Review: Bubble Sort

Key Action: Compares and swaps adjacent items.
Advantages: Simple to understand, easy to write in code, and requires very little additional memory.
Disadvantages: Very inefficient and slow for large lists because it performs many comparisons and swaps (worst-case time complexity is \( O(N^2) \)).

III. Merge Sort

Merge Sort is a much more efficient algorithm based on the divide and conquer strategy.

Analogy: Dividing the Work

Imagine you have a huge stack of unorganised test papers. Trying to sort the whole pile at once is overwhelming. Instead, you divide the pile in half, give each half to an assistant to split down and sort, and then neatly merge the sorted smaller piles back together.

How Merge Sort Works (Step-by-Step)

Merge Sort works in two distinct phases: the divide phase (splitting the lists) and the merge phase (recombining them in order).

1. The Divide Phase:
  1. Take the unsorted list and divide it into two equal (or near-equal) halves.
  2. Continue dividing each sub-list in half repeatedly until every sub-list contains only one single element.
  3. A list containing only one element is, by definition, already sorted.
2. The Merge Phase:
  1. Take adjacent single-item lists and merge them in pairs, comparing their elements so the new combined list is in sorted order.
  2. Repeat this merging process with pairs of two-item lists, four-item lists, and so on.
  3. Continue merging the sorted sub-lists until only one fully sorted list remains.
Quick Review: Merge Sort

Key Action: Recursively divides lists down to individual items and then merges them back in sorted order.
Advantages: Significantly faster and more consistent than Bubble sort for large datasets.
Disadvantages: More complex to understand and implement; requires additional memory space to hold the divided sub-lists during the merging process.

IV. Comparing Bubble Sort and Merge Sort

In Computer Science, comparing algorithms allows us to choose the right tool for a given problem. We primarily evaluate algorithms by their execution speed and efficiency on varying list sizes.

Comparison Summary

Feature Bubble Sort Merge Sort
Method Repeated adjacent comparisons and swaps. Divide and conquer (splitting and merging).
Speed / Efficiency Slow for large lists; time grows quadratically (\( O(N^2) \)). Fast and efficient for large lists.
Memory Usage Minimal extra memory needed (sorts in place). Requires additional memory to store sub-lists.
Implementation Simple and straightforward to write. More complex algorithm structure.

Key Takeaway

For very small lists, Bubble Sort is easy to write and perfectly adequate. However, for large amounts of data, Merge Sort is far superior because its running time grows at a much slower rate as the number of items (\( N \)) increases.

V. Quick Study Review

To succeed in exam questions on this topic, ensure you can trace both Bubble Sort and Merge Sort step-by-step on a small list (e.g., [6, 3, 8, 2, 5]) and clearly explain the advantages and disadvantages of each.

Memory Check

  • Bubble Sort: Look for adjacent pairs swapping positions until a pass with 0 swaps occurs.
  • Merge Sort: Look for splitting lists down to single items, followed by merging pairs into sorted order.

Keep practicing tracing these steps, and you will master sorting algorithms with confidence!