Merge sort is a sorting algorithm that recursively divides an array into half and then merges the subarrays back into a sorted array, hence the name.
Process
Pseudocode
Algorithm Mergesort(A): #A is an unsorted array
int size
size <- len(A)
If size <= 1 then:
Return A
Else:
List left ← Mergesort(A[1...size/2]) #Takes the left half of A
List right ← Mergesort(A[size/2...size]) #Right half of A
Return Merge(left,right)
End if
End Algorithm
Function Merge(L,R):
result ← List
#Compares the heads of L & R, then adds the smaller to the result
While L is NOT empty AND R is NOT empty do:
If first(L) <= first(R) then:
Append first(L) to result
L = rest(L)
Else:
Append first(R) to result
R = rest(R
End if
End do
#If L or R still contains values, empty them to result
While L is NOT empty do:
Append first(L) to result
L = rest(L)
End do
While R is NOT empty do:
Append first(R) to result
R = rest(R)
End do
End Function
Complexity Analysis
Time Complexity:
Merge sort has two main steps: recursive splitting and merging. The merging process is easy to analyse, as the merge subfunction always takes time (because the operations is proportional to the input size). The recursive splitting time can be solved via a recurrence relation. Since both halves of the array are used, the relation is as follows:
(for recursive splitting) (for merging, where c is a constant)
Using iteration to solve the relation:
The relation solves to : $O(n) + O(n*log(n))$ (dropping all constants) Since only the largest function is useful the final complexity is: $O(n \ log(n))$ ### Implementation