Merge Sort

Merge sort is often considered the ultimate sorting algorithm due to its optimization and reliability. While it may be slightly unintuitive, its logic is elegant, and its efficiency makes it a must-know for every developer.

Why Optimized?

With just a few lines of code, merge sort can consistently sort any array quickly, even with large datasets. It is one of the fastest algorithms, with a time complexity of O(n log n), and it supports other fast algorithms like Timsort.

Why Unintuitive?

Merge sort involves a recursive function, which can be unintuitive for some. If you're not familiar with recursion, you might want to refer to my guide on recursion here.

Implementation

Merge sort follows the divide and conquer strategy, consisting of two main steps: dividing and merging.

Step 1: Divide

The first step is to divide the array into subarrays until each subarray has only one element. This makes comparison straightforward and limits the number of iterations.

Step 2: Merge

Once the array is divided into subarrays of one element, we merge them while comparing the elements to ensure the resulting array is sorted.

To make the code cleaner and easier to understand, we'll break the algorithm into two functions: merge and mergeSort.

function merge(arr1, arr2) {
  let new_arr=  [];
  let i = 0;
  let j = 0;
  while (i < arr1.length && j < arr2.length) {
    if (arr1[i] < arr2[j]) {
      new_arr.push(arr1[i]);
      i++;
    } else {
      new_arr.push(arr2[j]);
      j++;
    }
  }

  if (i < arr1.length) {
    new_arr.push(...arr1.slice(i));
  }
  if (j < arr2.length) {
    new_arr.push(...arr2.slice(j));
  }
  
  return new_arr;
}

Explanation:

1. Initialization: We create an empty array new_arr to store the merged result and initialize two indexes i and j to 0.
2. Loop: We loop through both arrays, comparing the elements at the current indexes. The smaller element is pushed to new_arr, and the corresponding index is incremented.
3. Handling Remaining Elements: If one array is longer than the other, we push the remaining elements to new_arr.
4. Return: Finally, we return the merged array.

function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));

  return merge(left, right);
}

Explanation:

1. Base Case: If the array has only one element, we return it as it is already sorted.
2. Divide: We find the midpoint of the array and recursively call mergeSort on the left and right halves.
3. Merge: Once the base case is met, we merge the sorted left and right halves using the merge function.

To go into a little more detail, let's walk through the recursion step by step:

1. Initial Call: When mergeSort is first called with an array, it checks if the array length is greater than 1. If it is, it calculates the midpoint and recursively calls mergeSort on the left half of the array.
2. First Recursion: The left half of the array is further divided into two halves, and mergeSort is called on each of these halves. This process continues until the base case is met, i.e., when the subarray has only one element. At this point, the recursion starts to unwind.
3. Base Case: When a subarray with a single element is reached, it is returned as is because a single element is inherently sorted.
4. Merging Single Elements: As the recursion unwinds, the merge function is called to merge the single-element subarrays. For example, if we have two single-element arrays 3 and 1, the merge function compares these elements and merges them into a sorted array 1, 3.
5. Building Sorted Subarrays: This merging process continues as the recursion unwinds further. The sorted subarrays are merged into larger sorted subarrays. For instance, if we have two sorted subarrays 1, 3 and 2, 4, the merge function will merge them into a single sorted array 1, 2, 3, 4.
6. Final Merge: This process repeats until all the subarrays have been merged back into a single sorted array. Each level of recursion merges larger and larger subarrays until the entire array is sorted.

To illustrate this with an example, consider an array 3, 1, 4, 2:

• First Division: The array is divided into 3, 1 and 4, 2.
• Second Division: 3, 1 is divided into 3 and 1, and 4, 2 is divided into 4 and 2.
• Base Case: The single-element arrays 3, 1, 4, and 2 are returned as is.
• First Merge: 3 and 1 are merged into 1, 3, and 4 and 2 are merged into 2, 4.
• Second Merge: 1, 3 and 2, 4 are merged into 1, 2, 3, 4.

Performance considerations

Merge sort is one of the fastest sorting algorithms, suitable for any dataset size. Here are some key points to consider:

• Worst-case scenario: O(n log n) In the worst-case scenario, where the array is in reverse order, merge sort performs the same number of comparisons as the best-case scenario because the dividing step depends on the size of the input rather than the order.
• Best-case scenario: O(n log n) In the best-case scenario, where the array is already sorted, merge sort does not need to swap elements, but the number of dividing steps remains the same, resulting in a time complexity of O(n log n).
• Average-case scenario: O(n log n) On average, merge sort requires the same number of dividing steps and a significant number of comparisons and swaps, resulting in an average time complexity of O(n log n).

Practical Use Cases

Merge sort is suitable for most cases, but some algorithms may perform better in specific scenarios. For example, quicksort is often faster in practice, but merge sort is more consistent and stable.

Conclusion

Merge sort is a powerful and efficient sorting algorithm, especially for large datasets. While it may be challenging to understand initially, its performance is almost unmatched, with a time complexity of O(n log n) in all cases.

Thank you for your attention. I hope you learned something new. Writing this content also helps me clarify my understanding.

Happy coding!