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 worst-case 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 sub-arrays 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 sub-section of this array starting at index m and ending at index o, denoted as c[m..o]. Divide If n is the half-way 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) Best-case - O(n log n) typical, O(n) natural variant Average case - O(n log n) Worst-case 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