## Merge Sort

**Merge Sort** is essentially an algorithm similar to **Quick Sort**, using the **Divide and Conquer** strategy. It splits the input array in half equally first. After that, those are mixing in an ordered way.

An example of **Merge Sort**

If A = [7, 5 ,9, 3, 6, 2, 0, 4]

[7, 5, 9, 3, 6, 2, 0, 4] //Unsorted Array. [7, 5, 9, 3] [6, 2, 0, 4] //An array of 8 items is divided into two arrays of size 4. [7, 5] [9, 3] [6, 2] [0, 4] //Those two arrays divided into halves. [7] [5] [9] [3] [6] [2] [0] [4] //We further, divide those arrays and we achieve atomic value which can no more be divided. [5, 7] [3, 9] [2, 6] [0, 4] //Combine them in exactly the same manner as they were broken down. Then compare the element for each array and then combine them into another array in a sorted manner. [3, 5, 7, 9] [0, 2, 4, 6] //compare above sorted arrays and combine them in a sorted manner.[0, 2, 3, 4, 5, 6, 7, 9] //Merging two sorted arrays into one sorted array.

**Merging**

> Merging two or more sorted files into a third sorted file is known as merging.

> Three counters, I, J, and K, which are originally set at the beginning of each array, are required by the basic merge algorithm along with two input arrays, A and B, and an output array, C.

> The appropriated counters are advanced and the smaller of A[Actr], B[Bctr], is copied to the following item in C. The remainder of the other array is copied to C once either input array is exhausted.

**Merge Sort Algorithm**

mergeSort(Array A[0…n]){ if(n==1){ return A; } subArray1 = A[0]…A[n/2]; subArray2 = A[(n/2 )+1]…A[n]; subArray1 = mergeSort(subArray1); subArray2 = mergeSort(subArray2); return merge(subArray1, subArray2); } //An and Bn are the maximum number of elements of array A and B. merge(Array A, Array B){ Array C; Actr = 0; Bctr = 0; Cctr = 0; While (Actr<=An-1) and (Bctr<= Bn-1){ if A[Actr] < B[Bctr] { C[Cctr]=A[Actr] Actr++; }else{ C[Cctr]=B[Bctr] Bctr++; } Cctr++; } //Copy remaining elements from A While (Actr < An-1){ C[Cctr]=A[Actr]; Actr++; Cctr++; } //Copy remaining elements from B While (Bctr<= Bn-1){ C[Cctr]= B[Bctr]; Bctr++; Cctr++; } return C; }

**Merge Sort** worst-case time complexity being **Ο (n log n)**