merge-sort

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