O(1).Īnd to merge the subarrays, made by dividing the original array of n elements, a running time of O(n) will be required. In this section we will understand why the running time for merge sort is O(n*log n).Īs we have already learned in Binary Search that whenever we divide a number into half in every step, it can be represented using a logarithmic function, which is log n and the number of steps can be represented by log n + 1(at most)Īlso, we perform a single step operation to find out the middle of any subarray, i.e.
It is also a stable sort, which means the "equal" elements are ordered in the same order in the sorted list. Merge Sort is quite fast, and has a time complexity of O(n*log n). Let's consider an array with values as the array to be sorted.Ī = b // copying back the sorted list to a 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.Īnd then we have to merge all these sorted subarrays, step by step to form one single sorted array. So we will break these subarrays into even smaller subarrays, until we have multiple subarrays with single element in them. 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.īut breaking the orignal array into 2 smaller subarrays is not helping us in sorting the array. Combine the solutions of the subproblems to find the solution of the actual problem.Īs 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.The idea is to break down the problem into atomic subproblems, where they are actually solved. Conquer the subproblems by solving them.Divide the problem into multiple small problems.
The concept of Divide and Conquer involves three steps: Then, it repeatedly merges these subarrays, to produce new sorted subarrays, and in the end, one complete sorted array is produced. 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. 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. 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. So, they adopted the policy of Divide and Rule. When Britishers came to India, they saw a country with different religions living in harmony, hard working but naive citizens, unity in diversity, and found it difficult to establish their empire. If we can break a single big problem into smaller sub-problems, solve the smaller sub-problems and combine their solutions to find the solution for the original big problem, it becomes easier to solve the whole problem. Merge sort, on the other hand, runs in O(n*log n) time in all the cases.īefore jumping on to, how merge sort works and it's implementation, first lets understand what is the rule of Divide and Conquer? As the size of input grows, insertion and selection sort can take a long time to run. In the last two tutorials, we learned about Selection Sort and Insertion Sort, both of which have a worst-case running time of O(n 2). Merge Sort follows the rule of Divide and Conquer to sort a given set of numbers/elements, recursively, hence consuming less time.īefore moving forward with Merge Sort, check these topics out first:
0 kommentar(er)
