Merge Sort Algorithm Explained

Merge Sort is a highly efficient, stable sorting algorithm that follows the divide-and-conquer strategy. It works by recursively breaking down an unsorted list into smaller sublists until each sublist contains only one element (which is inherently sorted). Then, it repeatedly merges these sorted sublists to produce a final sorted list.

Steps involved in Merge Sort:

1. Divide: The unsorted list is divided into two roughly equal halves.
2. Conquer: Recursively sort the two sublists created in step 1.
3. Combine: Merge the two sorted sublists into a single sorted list.

Example:

Let's consider the unsorted list: [8, 3, 1, 7, 0, 10, 2]

1. Divide:

• Divide the list into two halves: [8, 3, 1, 7] and [0, 10, 2].

2. Conquer:

• Recursively sort the two sublists:
  • [8, 3, 1, 7] becomes [1, 3, 7, 8].
  • [0, 10, 2] becomes [0, 2, 10].

3. Combine:

• Merge the two sorted sublists: [1, 3, 7, 8] and [0, 2, 10] to produce [0, 1, 2, 3, 7, 8, 10].

Implementation:

function mergeSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }
  const mid = Math.floor(arr.length / 2);
  const leftArr = mergeSort(arr.slice(0, mid));
  const rightArr = mergeSort(arr.slice(mid));
  return merge(leftArr, rightArr);
}

function merge(leftArr, rightArr) {
  let resultArr = [];
  let leftIndex = 0;
  let rightIndex = 0;
  while (leftIndex < leftArr.length && rightIndex < rightArr.length) {
    if (leftArr[leftIndex] < rightArr[rightIndex]) {
      resultArr.push(leftArr[leftIndex]);
      leftIndex++;
    } else {
      resultArr.push(rightArr[rightIndex]);
      rightIndex++;
    }
  }
  // Add remaining elements from left or right array
  while (leftIndex < leftArr.length) {
    resultArr.push(leftArr[leftIndex]);
    leftIndex++;
  }
  while (rightIndex < rightArr.length) {
    resultArr.push(rightArr[rightIndex]);
    rightIndex++;
  }
  return resultArr;
}

Time and Space Complexity:

• Time Complexity: O(n log n) - Merge Sort consistently exhibits a time complexity of O(n log n) for both best, average, and worst-case scenarios.
• Space Complexity: O(n) - Due to the recursive nature and the creation of temporary arrays during the merging process, Merge Sort utilizes additional space proportional to the input size.

Advantages:

• Stable: Merge Sort preserves the relative order of elements with equal values.
• Efficient: O(n log n) time complexity for all cases.
• Well-suited for large datasets: Performs well on large lists.

Disadvantages:

• Space consumption: Requires additional memory for temporary arrays.
• Recursive: The recursive implementation can consume stack space.

Conclusion:

Merge Sort is a highly efficient sorting algorithm that shines due to its consistent time complexity and stable nature. While it requires additional space, its overall performance makes it a valuable sorting tool for many applications.