Learn Merge Sort Algorithm Like ABC w/ JavaScript
In software development, Merge Sort plays a crucial role in version control systems like Git. It ensures the seamless merging of branches by efficiently combining sorted lists of changes or commits. This process maintains the correct order and integrity of a project’s history, making Merge Sort indispensable for developers aiming to keep their projects well-organized and error-free.
Sorting algorithms like Bubble, Selection, and Insertion sorts have their charm, especially when dealing with small datasets, and cases where elements are partially sorted (best case). Their simplicity and ease of implementation make them go-to choices for introductory programming tasks.
However, when the size of the dataset grows, the worst-case time complexity of O(n²) becomes a bottleneck. They simply don’t scale up well with the size of the data.
This is where Merge Sort comes into play, showcasing its efficiency and scalability, particularly with larger datasets.
Understanding how the Merge Sort algorithm works
At its core, Merge Sort involves two primary actions:
1. Splitting and
2. Merging
Merge sort uses a divide-and-conquer approach. It begins by breaking down an array into smaller arrays, ideally until each small array consists of a single element or is empty. This is done because a single element (or an empty array) is inherently sorted. Merge Sort then proceeds to merge these small, sorted arrays into larger sorted arrays, continuing this process until the original array is reconstructed in a sorted manner.
The Splitting Phase
Splitting is the first phase of the Merge Sort algorithm. It involves dividing the array into two halves recursively until each sub-array contains a single element or is empty. Below is an implementation in Javascript using function expression:
const mergeSortWithSplitting = function (arr) {
// Base case: an array of 0 or 1 element is already sorted
if(arr.length <= 1){
return arr;
}
// Determine the middle point and split the array into two halves
let midIndex = Math.floor(arr.length / 2);
let leftHalf = arr.slice(0, midIndex);
let rightHalf = arr.slice(midIndex, arr.length);
// Recursively split the halves further
let sortedLeftHalf = mergeSortWithSplitting(leftHalf);
let sortedRightHalf = mergeSortWithSplitting(rightHalf);
// Merge the sorted halves
return mergeSplittedHalves(sortedLeftHalf, sortedRightHalf);
}NB: slice(start index, end index but not included)
The Merging Phase
The merging phase is where the true sorting happens. During this phase, two sorted arrays are combined into a single sorted array. This process requires careful comparison of elements from each array, ensuring that the resulting array maintains the sorted order. Find the implementation below:
const mergeSplittedHalves = function (leftHalf, rightHalf) {
let leftPointer = 0;
let rightPointer = 0;
let mergedResult = [];
// Compare elements from both arrays and add the smaller one to the result
while (leftPointer < leftHalf.length && rightPointer < rightHalf.length) {
if(leftHalf[leftPointer] < rightHalf[rightPointer]){
mergedResult.push(leftHalf[leftPointer]);
leftPointer++;
}
else {
mergedResult.push(rightHalf[rightPointer]);
rightPointer++;
}
}
// Append any remaining elements from either array to the result
while(leftPointer < leftHalf.length){
mergedResult.push(leftHalf[leftPointer])
leftPointer++;
}
while(rightPointer < rightHalf.length){
mergedResult.push(rightHalf[rightPointer])
rightPointer++;
}
return mergedResult;
}Testing the Merge Sort implementation
To demonstrate the effectiveness of our Merge Sort implementation, let’s test it with a sample array from the diagram above. This will allow us to see the algorithm in action and verify that it successfully sorts an array of integers, which can include both positive and negative values.
let arrayOfNumbers = [5, 2, 4, 7, 1, 3, 2, 6];
console.log('MergeSort Result 1:', mergeSortWithSplitting(arrayOfNumbers));
// OUTPUT: MergeSort Result 1: [ 1, 2, 2, 3, 4, 5, 6, 7 ]
arrayOfNumbers = [5, 2, 4, 7, 1, 3, 2, 6, -2];
console.log('MergeSort Result 2:', mergeSortWithSplitting(arrayOfNumbers));
// OUTPUT: MergeSort Result 2: [ -2, 1, 2, 2, 3, 4, 5, 6, 7 ]Analyzing Merge Sort’s efficiency
> Time Complexity
The elegance of Merge Sort lies in its time complexity of O(n log n), making it significantly more efficient for sorting large arrays compared to O(n²) sorting algorithms.
This efficiency stems from:
- Split Phase = O(log n)…because the array is divided in half repeatedly
- Merge Phase = O(m + n) = O(n)…because visiting each element in each array once
- Total time complexity = Split Phase * Merge Phase = O(n * log n) = O(n log n).
> Space Complexity
Merge Sort’s space complexity is a critical factor, especially for large datasets. Unlike in-place sorting algorithms, Merge Sort requires additional space for its operations because, during the merge phase, needs to allocate temporary arrays for merging sorted sub-arrays.
Space complexity = O(n)…where “n” is the number of elements in the array being sorted.
Core characteristics
- Divide and Conquer: Merge Sort offers O(n log n) time complexity for all cases (worst, average, and best), making it highly efficient and reliable for sorting large datasets.
- Non-In-place Sorting: Merge Sort requires additional space to hold the divided and merged parts of the array, leading to a space complexity of O(n).
In conclusion…
While Merge Sort offers excellent time efficiency with its O(n log n) complexity, its space complexity of O(n) means that it requires additional memory that grows linearly with the size of the input array.
Understanding this trade-off is crucial when choosing the right sorting algorithm for your specific needs, particularly in memory-constrained environments.
I hope you found this article useful. Feel free to clap, follow, or send comments, feedback, and questions :)
