Merge Sort 2

Merge sort works by dividing the dataset into two portions and applying merge sort on each half using this recursive technique. The base case is when there are two items in the dataset being considered. These can be ordered by exchange if needed.

Once all of the pairs of data have been sorted, then two pairs of sorted data can be merged.  As the recursion ‘unwinds’, larger pairs of sorted datasets can be merged. To illustrate this, consider the following dataset.

ADS 03 P2 N

Call mergesort with the full dataset (elements 0 to 7)

Mergesort checks the range to see if the base case has been reached.


if not
{
   call mergesort for the first half of the dataset
   call mergesort for the second half of the dataset
}
else
{
   sort data items
}
merge two data sets

For the first call of the function, the data is partitioned into two, one list of 6, 5, 8 and 1, and a second list of 4, 3, 7 and 2. The list (6 5 8 1) is then partitioned into two smaller lists (6 5 ) and (8 1). The base case has now been reached, and we can sort (6 5 ) into (5 6 ) and we can sort (8 1) into (1 8).

We can now merge (5 6) and (1 8). We compare 1 and 5, so the first element of the merged sequence is 1. We next compare 5 and 8, so the second element is 5. Next we compare 6 and 8 the third element will be 6, leaving 8 as the last element. The merged result is (1 5 6 8 ).

We now turn our attention to the second half of the original data set. Again we partition ( 4 3 7 2 ) into (4 3) and (7 2) . Sorting these we get (3 4) and (2 7) Merging these we get (2 3 4 7).

We now have two halves of the data sorted as (1 5 6 8) and (2 3 4 7). All that remains to be done is to merge the two halves together, giving us ( 1 2 3 4 5 6 7 8 ).

Next: Insertion and Deletion Algorithms