Merge sort
Let a be an
array of n numbers. Our aim is to sort this array in ascending order using
merge sort. The steps to be followed are
i)
Divide the array into n sub arrays with
size 1.
ii)
Merge adjacent pair of sub arrays [a[1]]
and [a[2]], [a[3]] and [a[4]], …….,
[a[n-1]] and [a[n]].
Now we will get a n/2 sorted sub arrays of size 2 or less.
iii)
Merge adjacent pairs of sub arrays
[a[1]] and [a[2]], [a[3]] and [a[4]], ……., [a[n-3]], [a[n-2]] and [a[n-1
iv)
Repeat this process until ther]], [a[n]].
Now we will get a n/4 sorted sub arrays of size 4 or less.e is only one sub
array of size n.
Now this array will be
in sorted order
Example
