How does merge sort work?
Merge sort
Merge sort is a kind of sorting technique which based on divide and conquer algorithm in computer programming. It is one of the most popular sorting algorithms and a great way to develop confidence in building recursive algorithms, and it is one of the most respected algorithms in worstcase time complexity being Ο(n log n). If the running time of merge sort for a list of length n is T(n), then the recurrence T(n) = 2T(n/2) + n.
Merging is the process of taking two smaller sorted lists and combining them together into a single, sorted, new list. In this key process that assumes that arr[l..m] and arr[m+1..r] are sorted and merges the two sorted subarrays into one.
Logic
function merge(left,right)
var list result
while length(left) > 0 or length(right) > 0
if length(left) > 0 and length(right) > 0
if first(left) <= first(right)
append first(left) to result
left = rest(left)
else
append first(right) to result
right = rest(right)
else if length(left) > 0
append first(left) to result
left = rest(left)
else if length(right) > 0
append first(right) to result
right = rest(right)
end while
return result
Divide and Conquer process in merge sort
By using the Divide and Conquer technique, we divide a problem into subproblems. Then we combine the results from the subproblem when each subproblem is ready after that will solve the main problem.
Suppose we had to sort an array C. C subproblem would be to sort a subsection of this array starting at index m and ending at index o, denoted as c[m..o].
Divide
If n is the halfway point between m and o, then we can split the subarray C[m..o] into two arrays C[m..n] and C[n+1, o].
Conquer
The next conquer step, we try to sort both the subarrays C[m..n] and C[n+1, o]. If we haven't yet reached the base case, we again divide both these subarrays and try to sort them.
Combine
When the conquer step reaches the base step and we get two sorted subarrays C[m..n] and C[n+1, o] for array C[m..o], we combine the results by creating a sorted array C[m..o] from two sorted subarrays C[m..n] and C[n+1, o].
As we already mention that merge sort first divides the array into equal halves and then combines them in a sorted manner.
Now let’s see how merge sort works through an example
To understand merge sort process, we take an unsorted array as the following −
First, merge sort divides the whole array iteratively into equal halves unless the atomic values are achieved. Here, an array of 8 items is divided into two arrays with four contain in each.
This does not change the sequence of appearance of items in the original. Now we divide above two arrays into halves.
In next step, we divide the arrays and we achieve undivided atomic value.
Then, we combine them in the same manner as they broke down.
After that, we compare the element for each list and then combine them into another list in a sorted manner. That 18 and 35 are in sorted positions. And compare 22 and 15 and in the target list of two values we put 15 first, and then 22. We change the order of 19 and 38 whereas 46 and 48 are placed sequentially.
Next iteration of the combining phase, we compare lists of two data values and merge them into a list of found data values placing all in a sorted order.
After the final merging, the list should look like this −
Finally, we learn some programming aspects of merge sorting.
Performance
Worst case  O(n log n)
Bestcase  O(n log n) typical, O(n) natural variant
Average case  O(n log n)
Worstcase space complexity  О(n) total with O(n) auxiliary, O(1) auxiliary with linked lists
Applications of Merge Sort

Merge Sort is useful for sorting linked lists in O(nLogn) time.

Used In inversion Count Problem

Used in External Sorting
Merge sort implementation in different programming languages
Merge Sort in C
Merge Sort in C++
Merge Sort in JAVA
Merge Sort in Python