- Merge sort is a sorting technique based on divide and conquer technique. With worst-case time complexity being Ο(n log n), it is one of the most used and approached algorithms.
- It is one of the most popular and efficient sorting algorithm. It divides the given list into two equal halves, calls itself for the two halves and then merges the two sorted halves.
- Merge sort is a divide-and-conquer algorithm based on the idea of breaking down a list into several sub-lists until each sub list consists of a single element and merging those sub lists in a manner that results into a sorted list.
- Merge sort is a recursive algorithm that continuously splits the array in half until it cannot be further divided i.e., the array has only one element left (an array with one element is always sorted). Then the sorted subarrays are merged into one sorted array.
Applications of Merge Sort:
- Sorting large datasets: Merge sort is particularly well-suited for sorting large datasets due to its guaranteed worst-case time complexity of O(n log n)
- .External sorting: Merge sort is commonly used in external sorting, where the data to be sorted is too large to fit into memory.
- Custom sorting: Merge sort can be adapted to handle different input distributions, such as partially sorted, nearly sorted, or completely unsorted data.
Advantages of Merge Sort:
- Stability: Merge sort is a stable sorting algorithm, which means it maintains the relative order of equal elements in the input array.
- Guaranteed worst-case performance: Merge sort has a worst-case time complexity of O(N logN), which means it performs well even on large datasets.
- Parallelizable: Merge sort is a naturally parallelizable algorithm, which means it can be easily parallelized to take advantage of multiple processors or threads.
Limitations of Merge Sort:
- Space complexity: Merge sort requires additional memory to store the merged sub-arrays during the sorting process.
- Not in-place: Merge sort is not an in-place sorting algorithm, which means it requires additional memory to store the sorted data. This can be a disadvantage in applications where memory usage is a concern.
- Not always optimal for small datasets: For small datasets, Merge sort has a higher time complexity than some other sorting algorithms, such as insertion sort. This can result in slower performance for very small datasets.
How Merge Sort Works?
To understand merge sort, we take an unsorted array as the following:
Step 1:
According to the merge sort, first divide the given array into two equal halves. Merge sort keeps dividing the list into equal parts until it cannot be further divided.
As there are eight elements in the given array, so it is divided into two arrays of size 4.
Step 2:
Now, again divide these two arrays into halves. As they are of size 4, so divide them into new arrays of size 2.
Step 3 :
Now, again divide these arrays to get the atomic value that cannot be further divided.
Step 4:
Now, combine them in the same manner they were broken.
In combining, first compare the element of each array and then combine them into another array in sorted order.
Step 5:
In the next iteration of combining, now compare the arrays with two data values and merge them into an array of found values in sorted order.
Step 6:
Now, there is a final merging of the arrays. After the final merging of above arrays, the array will look like
Now, the array is completely sorted.
Merge sort complexity:
1. Time Complexity
2. Space Complexity
The space complexity of merge sort is O(n). It is because, in merge sort, an extra variable is required for swapping.
