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 conqueralgorithmic 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