Merge Sort

If you don’t know what Merge Sort is then read all about it here.  Otherwise this programming tasks asks you to program a simple merge sort using recursion. Start by creating an array of random numbers that require sorting and pass it to your sorting method.

• If the list is of length 0 or 1, then it is already sorted. Otherwise:
• Divide the unsorted list into two sublists of about half the size.
• Sort each sublist recursively by re-applying merge sort.
• Merge the two sublists back into one sorted list.

Extension

A good extension for this task is to use timers and compare it with Bubble Sort which is a linear sort.  With larger arrays which is quicker?