Merge Sort
Pseudocode
Procedure MergeSort (Array(First..Last))
Begin
If Array contains only one element Then
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
Procedure Merge (LeftHalfArray(LHFirst..LHLast), RightHalfArray(RHFirst..RHLast))
Begin
Result: Array(ResultFirst..ResultLast) of size (LHLast-LHFirst+1+RHLast-RHFirst+1)
LeftPointer = LHFirst
RightPointer = RHFirst
ResultPointer = ResultFirst
Loop
If LeftHalfArray(LeftPointer) <= RightHalfArray(RightPointer)
Then
Result(ResultPointer) = LeftHalfArray(LeftPointer)
LeftPointer = LeftPointer + 1
ResultPointer = ResultPointer + 1
Else
Result(ResultPointer) = RightHalfArray(RightPointer)
RightPointer = RightPointer + 1
ResultPointer = ResultPointer + 1
Until all elements in either LeftHalfArray or RightHalfArray have been moved to Result
If all elements in the LeftHalfArray have been moved to Result Then
Move remaining elements in RightHalfArray to Result
Else
Move remaining elements in LeftHalfArray to Result
End If
Return Result
End Merge