Writing a Merge Sort in Pseudocode

Sorting algorithms are an essential part of computer science. When dealing with massive datasets, simple sorts like Bubble Sort become too slow. This is where Merge Sort shines.

Merge Sort is a highly efficient "divide and conquer" algorithm. Instead of trying to sort a massive array all at once, it repeatedly breaks the array down into smaller, more manageable halves until each half contains only one element. Then, it merges those tiny pieces back together in the correct order.

Because of its recursive nature, implementing a Merge Sort in pseudocode can feel intimidating. In this guide, we will break down the algorithm into spec-agnostic core concepts before looking at the specific syntax variations required by exam boards like AQA, OCR, and Cambridge (CIE).

Core Concepts: Divide and Conquer

Merge sort relies heavily on recursion—a subroutine calling itself. The algorithm has two distinct phases: splitting the data (Divide) and sorting/combining the data (Conquer).

The Divide Phase

The first step is finding the middle of the array and splitting it into a left half and a right half. This is done recursively until the subarrays are a single element long (and thus, technically "sorted").

The Conquer (Merge) Phase

Once the lists are broken down, we use pointers to iterate through the left and right halves. We compare the values at the pointers, and place the smaller value into the main array, incrementing the pointers as we go.

Syntax Variations by Exam Board

While the underlying algorithm of Merge Sort remains the same, the way you write the loops, selection statements, and subroutine definitions changes based on the exam board you are studying for.

AQA Pseudocode Standard

AQA expects capitalized control structures and the universal SUBROUTINE keyword. You'll rely on the LEN() function for array sizes and the arrow <- for assignments.

• Subroutines: SUBROUTINE MergeSort(arr).
• Length: LEN(arr).

OCR Pseudocode Standard

OCR syntax is Python-like, utilizing lowercase keywords like procedure and standard equals signs for assignment.

• Subroutines: procedure mergeSort(arr).
• Operators: Uses standard = for assignment and == for equivalence.

Cambridge (CIE / 9618) Standard

CIE requires strict data typing and explicit calling. If passing arrays to a sort, you must use the CALL keyword for the recursive steps and strictly declare your loop iterators.

• Subroutines: PROCEDURE MergeSort(BYREF MyArray : ARRAY).
• Calling: CALL MergeSort(LeftHalf).

The Full Algorithm Example

Below is a complete, working example of a merge sort algorithm structured cleanly in standard pseudocode. Note the cleanup loops at the end; these are necessary to catch any remaining elements if the left and right halves weren't exactly the same size.

Conclusion

While more complex than simpler sorts like Bubble or Insertion sort, the Merge Sort is incredibly powerful, boasting a time complexity of O(n log n). By understanding the divide (splitting arrays recursively) and conquer (merging them back in sequence) phases, the algorithm becomes logical and easy to reproduce.

Ensure you adapt the syntax—such as using `SUBROUTINE`, `CALL`, or specific iteration keywords—to match the expectations of your exam board.