Question

Give a complete pseudo-code description of the recursive merge-sort algorithm that takes an array as its input and output.

Short answer

Define mergeSort with a base case for arrays of length <= 1. Split the array, recursively sort each half, and merge them.

Step-by-step solution

Define the Merge-Sort Function

Create a function named mergeSort that takes an array as an input. This function will serve as the entry point for the merge sort algorithm.

Base Case for Recursion

In the mergeSort function, check if the length of the array is less than or equal to 1. If it is, return the array as it is already sorted.

Divide the Array

If the array length is greater than 1, find the middle index of the array. Split the array into two halves: left and right.

Recursive Calls

Recursively call mergeSort on both the left and right halves to further divide them until the base case is reached.

Merge Function

Create a helper function named merge that takes two sorted arrays (left and right) and merges them into a single sorted array.

Merging the Halves

Within the mergeSort function, call the merge function with the sorted left and right halves and return the sorted array.

Key concepts

recursive algorithms

A recursive algorithm repeatedly breaks down a problem into smaller instances of the same problem. The Merge Sort algorithm is a classic example of recursion.
The idea is to divide the array into smaller pieces recursively until each piece has only one element. An array with one element is simple because it's already sorted.
After breaking down the array, we start to merge them back together in the right order to get a fully sorted array.
This divide-and-conquer approach continues to ensure all smaller sub-arrays are sorted, eventually leading to the total array being sorted.

pseudo-code

Pseudo-code is a quick way to plan an algorithm without worrying about syntax rules of any particular programming language.
Here is how the Merge Sort algorithm can be described in pseudo-code:

mergeSort(array):
    if length of array <= 1
        return array
    find the middle index
    leftHalf = array from start to middle
    rightHalf = array from middle to end
    sortedLeft = mergeSort(leftHalf)
    sortedRight = mergeSort(rightHalf)
    return merge(sortedLeft, sortedRight)

merge(left, right):
    create an empty results array
    while left and right arrays are not empty:
        take the smaller element from left or right
        append this element to the results array
    if left is not empty
        append remaining left elements to results
    if right is not empty
        append remaining right elements to results
    return results

Each line of the pseudo-code is straightforward and shows the sequence of steps involved.

array division

The first essential step in the Merge Sort is dividing the array.
If the array length is more than one, you need to split it.
Find the middle index: Calculate the middle using integer division. For an array of length n, the middle index is given by \(\text{middle} = \frac{\text{n}}{2}\).
Split the array into two halves: Create two new arrays, left and right. The left array contains elements from the start to the middle index. The right array contains elements from the middle to the end.

Example: For array [4, 2, 1, 3], the middle index is 2. Split the array as follows -
left: [4, 2]
right: [1, 3]

By continuing to split arrays into smaller sub-arrays, we eventually reach arrays with only one element.

merging sorted arrays

The last step of the Merge Sort is to merge the sorted arrays. This is handled by the merge function.
How merging works:

• Initialize an empty results array.
• Compare the first elements of both left and right arrays.
• Place the smaller element into the results array.
• Remove the added element from its original array.

Repeat these steps until all elements from the left and right arrays are added to the results array.
If any elements are left in either array, append those to the results array too.

Example: Merging [2, 4] and [1, 3]
1 is smaller than 2, so results: [1]
2 is smaller than 3, so results: [1, 2]
3 is smaller than 4, so results: [1, 2, 3]
All elements added, results: [1, 2, 3, 4]

This ensures that the merging step produces a sorted array.