Merge sort how does it work

Log In using. Toggle navigation. Forgot Password. Go To Problems. Level 2 Arrays. Arrays In Programming Fundamentals. Merge Sort Algorithm Merge sort is one of the most efficient sorting algorithms. Like Us Follow Us Email. Please note the color codes given to these lists. We first compare the element for each list and then combine them into another list in a sorted manner. We see that 14 and 33 are in sorted positions. We compare 27 and 10 and in the target list of 2 values we put 10 first, followed by We change the order of 19 and 35 whereas 42 and 44 are placed sequentially.

Merge sort accesses data sequentially and the need of random access is low. Merge sort algorithm requires an additional memory space of 0 n for the temporary array. It goes through the whole process even if the array is sorted. Recent Articles on Merge Sort Coding practice for sorting.

Skip to content. Change Language. Related Articles. Table of Contents. Save Article. Improve Article. Like Article. Python program for implementation of MergeSort. Finding the mid of the array. So, they adopted the policy of Divide and Rule. Where the population of India was collectively a one big problem for them, they divided the problem into smaller problems, by instigating rivalries between local kings, making them stand against each other, and this worked very well for them.

Well that was history, and a socio-political policy Divide and Rule , but the idea here is, if we can somehow divide a problem into smaller sub-problems, it becomes easier to eventually solve the whole problem. In Merge Sort , the given unsorted array with n elements, is divided into n subarrays, each having one element, because a single element is always sorted in itself.

Then, it repeatedly merges these subarrays, to produce new sorted subarrays, and in the end, one complete sorted array is produced. As we have already discussed that merge sort utilizes divide-and-conquer rule to break the problem into sub-problems, the problem in this case being, sorting a given array.

In merge sort, we break the given array midway, for example if the original array had 6 elements, then merge sort will break it down into two subarrays with 3 elements each. So we will break these subarrays into even smaller subarrays, until we have multiple subarrays with single element in them. Now, the idea here is that an array with a single element is already sorted, so once we break the original array into subarrays which has only a single element, we have successfully broken down our problem into base problems.