Algorithm

Merge Sort

All you need to know >>

Merge sort is one of the most efficient sorting techniques and it’s based on the “divide and conquer” paradigm.

In Mergesort, we take the mid index which is (beg index + end index)/2. Our array will always break into two subsequent arrays with approximately equal length.

The Algorithm

Best Time Complexity: O(nlogn) Average Time Complexity: O(nlogn) Worst Time Complexity: O(nlogn)

Time Complexity

'n' auxiliary space is required in Merge Sort implementation as all the elements are copied into an auxiliary array. Hence, Space Complexity is: O(n)

Space Complexity

The Difference

QuickSort Splitting of the array depends on the value of pivot and other array elements. It is non-stable. Merge Sort Splitting of array generally done on half It is stable.