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))
If Array contains only one element Then
Return Array
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
End MergeSort


The merge sort algorithm:


1. Divide the list in half


2. Merge sort the first half


3. Merge sort the second half


4. Merge both halves back together