- Time Complexity:
O(nlogn)in all scenarios
- Space Complexity:
O(n + log(n))simplified to
- Not In-Place
Merge sort is a divide and conquer technique. Given an array, we repeatedly divide it into 2 arrays, till we have one element of concern. At the point, that single element will be sorted.
Now, we proceed to merge the divided sections of the array. When merging, we create a temporary array to hold the items from the 2 arrays we are merging. We will have 2 pointers
j to track the current index of array 1 and array 2. In each iteration, we compare the index pointed to by the pointer
i in array 1 to that of the index of array 2 by pointer
j. Whichever element is the smaller one, we copy that into the temporary array.
At the end of the merge process, there maybe left over elements in either array, so we just copy them over into the temporary array. At the end of the merge process, we would have merged both arrays into one sorted array.
Now, we need to copy whatever elements are in the temporary array back into the original array starting from index
Time taken to merge 2 portions of the array will be
Let mergeSort take a time complexity of
T(n). Due to the 2 calls to mergeSort for the 2 halves of the array and subsequently to merge function which takes
T(n) can be represented as follows:
T(n) = 2 * T(n/2) + O(n)
For every call to
merge(), there will be a time complexity of
O(n). We are making
log(n) such calls due to the depth of the recursive call stack.
T(n) simplifies to an order of
Note: There is no best/worst case for merge sort. Therefore, despite the initial condition of the list, already sorted, reverse sorted etc., merge sort will still take the same time complexity of
Note that merge sort is not an in-place sort, which means it requires extra space. This extra space is required in the merge algorithm where we need to copy the elements from the original array into a temporary array. This takes
Apart from a temporary, we also need to consider the recursion stack involved. Note that thought each call to
mergeSort has 3 sub-functions, not all the recursive calls occur simultaneously. Since it is a divide and conquer algorithm, we need
ceil(log(n)) + 1, which simplifies to
O(log(n)) space for the stack.
The total space complexity is therefore given by
O(n + log(n)) which is dominated by the
O(n) term, and hence simplifies to