Merge Sort (OCR A Level Computer Science)

Merge sort

What is a Merge Sort?

• Merge sort is an example of a divide and conquer algorithm that reduces the size of the problem into smaller problems that are more easily solvable by an algorithm

• Specifically, the merge sort divides the list in half, creating two sub lists. Each sub list is then divided into two until each sub list contains only one item or element

• Groups of two sub lists are then sorted and merged together to form new, larger sub lists until all sub lists have been merged into a single sorted list

• The merge sort therefore contains two parts:

  • Part one: Divide the list into sub lists until each sub list contains only one element

  • Part two: Repeatedly merge groups of two and sort them, until all lists have been merged into a single sorted list

• The merge sort has been illustrated below using a list of ten items: [15, 5, 2, 7, 4, 9, 10, 1, 8, 3]

Performing the Merge sort

Figure 1: Performing the Merge sort

• Notice that halving the list sometimes produces odd numbers of elements in sub lists. When dividing, all sub lists must contain a single element before merging can begin.

• When merging, only two sub lists can be merged at a time. Any left over sub lists are merged in the next merging iteration

• In order to merge two sub lists, two pointers are required, one for each sub list. The pointer keeps track of which elements are to be compared. Once an element has been merged into the new list, the corresponding pointer is incremented. The process continues until a list contains no elements to compare, at which point the remaining elements are appended to the end of the new merged sub list.

Time Complexity of a Merge Sort

• To determine the algorithm's execution time as measured by the number of instructions or steps carried out Big-O notation must be used

• The time complexity of a merge sort is dependent on its divide and conquer nature O(logn) and the fact that n sub lists must be merged. This means the overall worst case time complexity of the merge sort is O(nlogn)

• The best case and average case scenario time complexity of the merge sort is O(nlogn) as regardless of the number of elements or item, n must still be merged and halved

Space Complexity of a Merge Sort

• The merge sort requires twice the amount of space of other sorting algorithms due to holding copies of the left and right halves of the list. Its space complexity is therefore O(n) original space and an additional O(n) space to store the copies of the list

Tracing a Merge Sort

• In the trace table below, several calls to merge sort are made which splits the list. Each call generates a stack frame which is put on the stack. Stack frames are removed when the current stack frame reaches the end of its code

• The list is gradually broken down into sub lists, starting with the left side of each sub list. Sub lists are created until each sub list contains only one element which is the base case. When a base case is reached the stack frame is removed and the program continues execution on the line after the call to merge sort

• Each sub list is gradually merged, two at a time and passed up the stack to be merged with another sub list in a later merge sort call

• Pointers are incremented during the merge such that the next element to merge in each sub list is tracked and appropriately added to the new list. NewListPointer tracks the position of elements in the new list

• Row 25 shows the algorithm completing the left side of the list and the beginning of the merge of the right sub list which repeats the process outlined in the trace table

Trace Table for the Merge Sort

Implementing a merge sort

Pseudocode

procedure mergesort(list)
	if len(list) > 1 then
		mid = len(list) div 2
		left = list[:mid]
		right = list[mid:]
		
		mergesort(left)
		mergesort(right)
		
		leftPointer = 0
		rightPointer = 0
		newListPointer = 0
		while leftPointer < len(left) and rightPointer < len(right)
			if left[leftPointer] < right[rightPointer] then
				list[newListPointer] = left[leftPointer]
				leftPointer = leftPointer + 1
			else
				list[newListPointer] = right[rightPointer]
				rightPointer = rightPointer + 1
			endif
		
			newListPointer = newListPointer + 1
		endwhile
		
		while leftPointer < len(left)
			list[newListPointer] = left[leftPointer]
			leftPointer = leftPointer + 1
			newListPointer = newListPointer + 1
		endwhile

		while rightPointer < len(right)
			list[newListPointer] = right[rightPointer]
			rightPointer = rightPointer + 1
			newListPointer = newListPointer + 1
		endwhile
	endif
endprocedure

list = [15, 5, 2, 7, 4, 9, 10, 1, 8, 3]
mergesort(list)
print(list)

• It is important to note that the merge sort uses [popover id="N-tIO9JV~O-0w97n" label="recursion"] in order to work. To divide the list into sub lists, the merge sort algorithm must call itself, using a [popover id="5UjdORCO7kg2tW1L" label="base case"] of one element. Repeated calls to the algorithm are put on the [popover id="vZKPSwu5BsgHPpV_" label="stack"]. Once each list is composed on one element, [popover id="eAY1NI_y6NFvH4Le" label="stack frame"] are removed from the stack and processed

• It is furthermore important to note that [:mid] means “all elements up to but not including the mid value” and [mid:] means “all elements starting from and including the mid value”

  • This technique is known as slicing

• Once the list has been split, and no more recursive calls are made, three new variables are defined per stack frame:

  • leftPointer (keeps track of the left sub list)

  • rightPointer (keeps track of the right sub list)

  • newListPointer (keeps track of the next available space in the sorted list)

• The new list is merged in two stages:

  • Stage one: Merge all elements until one list is empty

    • The first while loop manages this process. The left and right pointers increment over the left and right lists, comparing elements one at a time. If one is smaller than the other then it is placed in the next available space in the new list

  • Stage two: Append the non-empty list's remaining elements to the new list

    • This is managed by the final two while loops. One merges if the left half has remaining elements. The other merges if the right half has remaining elements. Only one will be called, not both

Python

def merge_sort(list):
  if len(list) > 1:
    mid = len(list) // 2
    left = list[:mid]
    right = list[mid:]
    merge_sort(left)
    merge_sort(right)
    left_pointer, right_pointer, new_list_pointer = 0, 0, 0
    new_list = [None] * len(list)
    while left_pointer < len(left) and right_pointer < len(right):
      if left[left_pointer] < right[right_pointer]:
        new_list[new_list_pointer] = left[left_pointer]
        left_pointer = left_pointer + 1
      else:
        new_list[new_list_pointer] = right[right_pointer]
        right_pointer = right_pointer + 1
      new_list_pointer = new_list_pointer + 1
    while left_pointer < len(left):
      new_list[new_list_pointer] = left[left_pointer]
      left_pointer = left_pointer + 1
      new_list_pointer = new_list_pointer + 1
    while right_pointer < len(right):
      new_list[new_list_pointer] = right[right_pointer]
      right_pointer = right_pointer + 1
      new_list_pointer = new_list_pointer + 1
    list[:] = new_list
  return list

list = [15, 5, 2, 7, 4, 9, 10, 1, 8, 3]
merge_sort(list)
print(list)  # Output: [1, 2, 3, 4, 5, 7, 8, 9, 10, 15]

Java

public class MergeSort {

    public static void mergeSort(int[] data) {
        if (data.length > 1) {
            int mid = data.length / 2;
            int[] left = new int[mid];
            int[] right = new int[data.length - mid];
            System.arraycopy(data, 0, left, 0, mid);
            System.arraycopy(data, mid, right, 0, data.length - mid);
            mergeSort(left);
            mergeSort(right);
            merge(data, left, right);
        }
    }

    private static void merge(int[] data, int[] left, int[] right) {
        int leftPointer = 0, rightPointer = 0, newListPointer = 0;
        while (leftPointer < left.length && rightPointer < right.length) {
            if (left[leftPointer] < right[rightPointer]) {
                data[newListPointer] = left[leftPointer];
                leftPointer++;
            } else {
                data[newListPointer] = right[rightPointer];
                rightPointer++;
            }
            newListPointer++;
        }
        System.arraycopy(left, leftPointer, data, newListPointer, left.length - leftPointer);
        System.arraycopy(right, rightPointer, data, newListPointer, right.length - rightPointer);
    }

    public static void main(String[] args) {
        int[] data = {15, 5, 2, 7, 4, 9, 10, 1, 8, 3};
        mergeSort(data);
        System.out.println(Arrays.toString(data));  // Output: [1, 2, 3, 4, 5, 7, 8, 9, 10, 15]
    }
}