Merge sort is a sort algorithm for rearranging lists (or any other data structure that can

only be accessed sequentially, e.g. file streams) into a specified order. It is a particularly

good example of the divide and conquer algorithmic paradigm. Merge sort has an

average and worst-case performance of O(n log(n)).

The Algorithm Pseudocode:

MergeSort (Array(First..Last))
Begin
If Array contains only one element Then
     Return Array
Else
     Middle= ((Last + First)/2) rounded down to the nearest integer
     LeftHalfArray = MergeSort(Array(First..Middle)) 
     RightHalfArray = MergeSort(Array(Middle+1..Last)) 
     ResultArray = Merge(LeftHalfArray, RightHalfArray) 
     Return ResultArray
EndIf
End MergeSort