## Algorithm/Insights

Merge sort is a comparison based algorithm that uses divide and conquer approach to sort an array in O(n logn) time.

Merge sort is a stable sort i.e. it preserves the order of same array elements after sorting.

Algorithm for Merge sort is:

Step 1. Divide the array into 2 halves recursively.

Step 2. Merge the divided parts in sorted order.

Here is an example that explains the algorithm:

First, the array {12, 35, 87, 26, 9, 28, 7} is divided to sub arrays {12, 35, 87, 26} and {9, 28, 7} as shown in the image above.

Then {12, 35, 87, 26} is divided into {12, 35} and {87, 26}.

Next {12, 35} is divided into {12} and {35}

At this step, no further division is possible on single element arrays {12} and {35}.

Next step is to merge these arrays in sorted order to get {12, 35}

Next {87, 26} is divided into {87} and {26}

Similar as above, we merge these single element arrays in sorted order to get {26, 87}

Now we are at the step where we have {12, 35} and {26, 87}. We merge these subarrays in sorted order to form sorted array: {12, 26, 35, 87}

Similarly, {9, 28, 7} is also first divided recursively and then merged in sorted order to get sorted array {7, 9, 28}

Finally, we merge sorted subarrays {12, 26, 35, 87} and {7, 9, 28} in sorted order to get the sorted array {7, 9, 12, 26, 28, 35, 87}.

Here is the algorithm for merging 2 sorted arrays used by merge sort algorithm given in the code snippet section:

1. Create temporary arrays temp1 and temp2.

2. Copy elements of first subarray to temp1. So, temp1 = {12, 26, 35, 87}

3. Copy elements of second subarray to temp2. So, temp2 = {7, 9, 28}

4. Now copy elements from temp1 and temp2 to the original array in sorted order:

a. Traverse arrays temp1 and temp2 together:

b. If temp1[i] <= temp2[j], then copy temp1[i] to the original array and move i to next element in temp1.

c. Else copy temp2[j] to the original array and move j to next element in temp2.

d. If end of one temporary array is reached, then copy the elements of the other temporary array to the original array in the same order.