Merge Sort Algorithm

Merge Sort is a sorting algorithm that implement divide and conquer method. It generally use to motivates guiding principles for algorithm analysis (worst-case and asymptotic analysis) and also provide the analysis generalizes to “Master Method”. (PS: algorithm also known as Pseudocode.)

Purpose of merge sort:
If you given an arrays of n numbers that is unsorted for example like "5,4,1,8,7,2,6,3", you are required have the output of the same number arrays sorted in increasing order like"1,2,3,4,5,6,7,8".

Illustrate how merge sort work

How Merge sort Work?

1. The arrays will divide into half
2. Recursively  sort the first half of the input array
3. recursively sort the second half of the input array
4. Merge the 2 sorted half array into 1 like the picture above.

Pseudocode for Merge:

C = output [length = n]
A = 1st sorted array [n/2]
B = 2nd sorted array [n/2]
i = 1
j = 1


for k = 1 to n
if A(i) < B(j)
C(k) = A(i)
i++
else [B(j) < A(i)]
C(k) = B(j)
j++
end

Running time

Running time of merge sort is depend on the number of lines of code executed. It also can say the running time to sort m number (running time<=4m+2) or (running time<6m) since (m >=1)

For ever input array of m numbers,merged sort produces a sorted arrays and uses maximum 6nlog₂n+6n operation.