Merge Sort

Merge Sort is a well-known, efficient, and stable sorting algorithm that follows the divide-and-conquer approach. It splits the array into smaller sub-arrays, sorts them, and then merges them back into a fully sorted array. With a time complexity of O(n log n), Merge Sort is significantly faster than simpler algorithms like Bubble Sort and Selection Sort, especially for larger datasets.

How Merge Sort Works:

1. Divide: Recursively divide the array into two halves until you have sub-arrays with only one element.

2. Conquer: Merge each pair of sub-arrays, sorting their elements.

3. Combine: Continue merging sorted sub-arrays until the entire array is sorted.
   

   JavaScript Code Implementation:

   Here’s an alternate way to implement Merge Sort in JavaScript, but this time we focus on a more detailed breakdown with fewer helper functions:

   function mergeSort(arr) {
     // If the array contains a single element, it's already sorted
     if (arr.length < 2) return arr;
   
     // Split the array in two halves
     const mid = Math.floor(arr.length / 2);
     const left = arr.slice(0, mid);
     const right = arr.slice(mid);
   
     // Recursively split and merge each half
     return mergeArrays(mergeSort(left), mergeSort(right));
   }
   
   function mergeArrays(left, right) {
     let sortedArray = [], i = 0, j = 0;
   
     // Merge while both arrays have elements
     while (i < left.length && j < right.length) {
       if (left[i] < right[j]) {
         sortedArray.push(left[i++]);
       } else {
         sortedArray.push(right[j++]);
       }
     }
   
     // Merge remaining elements from left or right arrays
     return [...sortedArray, ...left.slice(i), ...right.slice(j)];
   }
   
   // Example usage:
   const arr = [38, 27, 43, 3, 9, 82, 10];
   const sorted = mergeSort(arr);
   console.log(sorted); // Output: [3, 9, 10, 27, 38, 43, 82]

   Key Points:

   • mergeSort splits the array recursively.

   • mergeArrays compares elements from both sub-arrays and merges them in sorted order.

Merge Sort Steps:

Let’s go through an example with an array [38, 27, 43, 3, 9, 82, 10]:

1. Initial Array: [38, 27, 43, 3, 9, 82, 10]

2. Split Array:

   • [38, 27, 43] and [3, 9, 82, 10]

   • Continue splitting: [38], [27, 43] → [27], [43]

   • [3], [9, 82, 10] → [9], [82, 10] → [82], [10]

3. Merge and Sort:

   • Merge [27] and [43] → [27, 43]

   • Merge [82] and [10] → [10, 82]

   • Continue merging until fully sorted → [3, 9, 10, 27, 38, 43, 82]

Merge Sort Advantages:

• Efficiency: With a time complexity of O(n log n), it’s suitable for larger datasets.

• Stability: The relative order of equal elements remains the same.