ALKO

Merge sort

Overview

Mergesort is a recursive algorithm that splits an input of nn elements into nn subarrays (each considered to be sorted as they have only 11 element) then repeatedly merges them.

Any two sorted arrays can be sorted in linear time by iterating over each array and selecting the smaller element each time.

Visualization

99
55
77
1010
22
Input
Input size n=5n=5:
99
55
77
1010
22
AA
55
LL
22
RR
Step 0/28

Pseudocode

Algorithm Merge Sort
1:
procedure MergeSort(A)(A)
2:
if ∣A∣=1|A| = 1 then
3:
return AA
4:
m←⌊∣A∣2⌋m\gets\left\lfloor\frac{|A|}{2}\right\rfloor
5:
L←L \gets MergeSort(A[...m])(A[...m])
6:
R←R \gets MergeSort(A[m+1...])(A[m+1...])
7:
return Merge(L,R)(L, R)
'
'
8:
procedure Merge(L,R)(L, R)
9:
i,j,k←0i, j, k \gets 0
10:
while i<∣L∣i < |L| and j<∣R∣j < |R| do
11:
if l[i]<r[j]l[i] < r[j] then
12:
A[k]←L[i]A[k] \gets L[i]
13:
i←i+1i \gets i + 1
14:
else
15:
A[k]←R[j]A[k] \gets R[j]
16:
j←j+1j \gets j + 1
17:
k←k+1k \gets k + 1
18:
while i<∣L∣i < |L| do
19:
A[k]←L[i]A[k] \gets L[i]
20:
i←i+1i \gets i + 1
21:
k←k+1k \gets k + 1
22:
while j<∣R∣j < |R| do
23:
A[k]←R[j]A[k] \gets R[j]
24:
j←j+1j \gets j + 1
25:
k←k+1k \gets k + 1
26:
return AA

Time Complexity

The time complexity of merge sort is Tn=Tn2+nT_n = T_{\frac{n}{2}} + n as at each iteration, we divide the problem into two subproblems of half the size and merge them in linear time.

Therefore the time complexity is O(nlog⁡n)O(n \log n) by the master theorem.