Merge Sort
➤Merge sort is a divide-and-conquer sorting algorithm that recursively divides an array into smaller subarrays, sorts them individually, and then merges them back together in a sorted manner. It achieves a time complexity of O(n log n) and is stable, making it suitable for large datasets.
How Merge-sort works?
1.Divide: The unsorted array is recursively divided into smaller subarrays until each subarray contains only one element.
2.Merge: The subarrays are then merged back together in a sorted manner. This process begins with merging pairs of subarrays and continues until the entire array is sorted.
2.1. Take two adjacent subarrays and compare the elements at corresponding positions.
2.2. Place the smaller element into a temporary array and move to the next element in that subarray.
2.3. Repeat the comparison and placement process until one of the subarrays is fully processed.
2.4. Copy the remaining elements from the other subarray directly into the temporary array.
2.5. Replace the original subarray with the sorted elements from the temporary array.
.gif)
How the element compare?
Demonstration of Merge Sort
Optimized Bubble sort Algorithm
1.Insertion Sort for Small Subarrays:
Instead of recursively dividing the array until each subarray
contains only one element, the algorithm switches to Insertion Sort when the subarray size becomes small
(e.g., below a certain threshold). This reduces the overhead of recursive calls and performs better on smaller
or partially sorted subarrays.
2.Skipping Unnecessary Merging:
During the merging process, the algorithm checks if the last element of the left
subarray is already smaller than or equal to the first element of the right subarray. If true, it means the subarrays are already
sorted, and the merging step can be skipped. This optimization reduces unnecessary comparisons and improves performance.
3.Reuse of Auxiliary Array:
Instead of creating a new temporary array for each merge operation, the algorithm allocates
a single auxiliary array at the beginning and reuses it throughout the sorting process. This eliminates the overhead of repeated memory
allocation and deallocation, making the algorithm more efficient.
4.Bottom-Up Merge Sort:
The algorithm can be implemented iteratively using a bottom-up approach. It starts with subarrays
of size 1 and merges them to form larger sorted subarrays. This eliminates the need for recursive calls and can be more cache-friendly,
as it works on adjacent elements. This approach further improves performance.
2.1. Take two adjacent subarrays and compare the elements at corresponding positions.
2.2. Place the smaller element into a temporary array and move to the next element in that subarray.
2.3. Repeat the comparison and placement process until one of the subarrays is fully processed.
2.4. Copy the remaining elements from the other subarray directly into the temporary array.
2.5. Replace the original subarray with the sorted elements from the temporary array.
| Algorithm | Time complexity |
|---|---|
| Best Case | O(n(logn)) |
| Average Case | O(n(logn)) |
| Worst Case | O(n(logn)) |