As with any recursive algorithm, we need to set up a base case. We’re going to implement Merge Sort using Recursion. Generally speaking, Merge Sort has a Time Complexity of O(nlog(n)) and a space complexity of O(n). I won’t cover these solutions here but you can have a look here and here to understand how they work. Another solution can give you O(1) space. There is another method to use an auxiliary array (a copy of the original array) to help with sorting in-place, which would give a solution with the same time complexity and O(n) auxiliary space. The summation of every level of division and merge will give you a time complexity of O(nlog(n)). Dividing those halves into halves, will give you O(n/4), and so on.
Merge sorty full#
At the first step of dividing the full array and the eventual merging all the values into a new array, it will take O(n).Īfter dividing the array in halves, each half will be n/2 in size and will take O(n/2). If you add the summation of every level of dividing and merging, you will have an O(nlog(n)) space complexity for this solution.įor time complexity, you can look at your operations in the same way. We continue to split those arrays as well O(n/4). If you split that array in half, it will take O(n/2) to divide and merge that half and O(n/2) to divide and merge the other half. We know that it takes O(n) to divide and eventually merge the full array. Each call to merge sort that causes whatever part we are working on to be split in two and make new arrays to sort those subarrays. We also have to take into account that all of the actions of splitting and merging that happen before we reach the final result. Our space complexity will be O(n) just to hold the values of the new array. When we split the original array into subarrays and eventually return a new array of size n. Continue to merge arrays back until you have a new array the same size as the original array but in sorted order. Once you have reached that point, you need to merge those values into a new array. To sort an array with Merge Sort, you must continue to divide the problem into subproblems until your subproblems (your base case) are of size 1. We now have a sorted array! Time and Space Complexity Let’s go back to the array example that we’ve used in our previous sections: Until you reach the point where you cannot divide halves any further and you only have two values to compare.Ĭomparing two values is easy right? Once you compare the two values, we can merge them together in the right order!
How do you sort the halves? You divide them again.
We take our input array, divide it in half, and then sort each of those halves and join them back together. Merge Sort is a Divide-and-Conquer algorithm. Understandably, to obtain this efficiency, Merge Sort is a bit more complex than other sorting sorting algorithms like Bubble Sort, Insertion Sort, and Selection Sort. Merge Sort is an efficient algorithm used to sort lists of values.
Merge sorty series#
The sorting algorithms I’ll be covering in this series are:
Merge sorty software#
If you are preparing for software engineering interviews, it’s very likely that one or more sorting algorithms may come up during your interviews. Most programming languages will come with a built-in sort function but in order to write better code, you need to know what’s going on in the background. Int merged = mergeSort(arr, 0, arr.Let’s Sort! In this series, I’ll be covering sorting algorithms. Merge sort repeatedly breaks down an array into several subarrays until each subarray consists of a single element and merging those subarrays in a manner that results in a sorted array. When the base case is hit, we start merging the left part and the right part and we get a sorted array at the end. The base case here is reaching one single element. then those arrays are further divided till we reach a single element. Repeat the process till a single sorted array is obtained.Īn array of Size ‘N’ is divided into two parts ‘N/2’ size of each.Take adjacent pairs of two single-element array and merge them to form an array of 2 elements.
The idea is to break down the problem into atomic subproblems, where they are actually solved. Divide the problem into multiple subproblems.