Merge Sort Implementation

JavaScript Implementation

function mergeSort(arr) {
  // Base case: arrays with 0 or 1 element are already sorted
  if (arr.length <= 1) {
    return arr;
  }
  
  // Split the array into two halves
  const middle = Math.floor(arr.length / 2);
  const left = arr.slice(0, middle);
  const right = arr.slice(middle);
  
  // Recursively sort and merge the two halves
  return merge(
    mergeSort(left), 
    mergeSort(right)
  );
}

// Helper function to merge two sorted arrays
function merge(left, right) {
  let result = [];
  let i = 0, j = 0;
  
  // Compare elements from both arrays and add smaller one to result
  while (i < left.length && j < right.length) {
    if (left[i] < right[j]) {
      result.push(left[i++]);
    } else {
      result.push(right[j++]);
    }
  }
  
  // Add any remaining elements
  return result.concat(left.slice(i)).concat(right.slice(j));
}

// Usage example
let array = [38, 27, 43, 3, 9, 82, 10];
console.log(mergeSort(array)); // [3, 9, 10, 27, 38, 43, 82]

Python Implementation

def merge_sort(arr):
    # Base case: arrays with 0 or 1 element are already sorted
    if len(arr) <= 1:
        return arr
    
    # Split the array into two halves
    middle = len(arr) // 2
    left = arr[:middle]
    right = arr[middle:]
    
    # Recursively sort and merge the two halves
    left = merge_sort(left)
    right = merge_sort(right)
    
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    
    # Compare elements from both arrays and add smaller one to result
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    
    # Add any remaining elements
    result.extend(left[i:])
    result.extend(right[j:])
    
    return result

# Test
array = [38, 27, 43, 3, 9, 82, 10]
print(merge_sort(array))  # [3, 9, 10, 27, 38, 43, 82]

C++ Implementation

#include <iostream>
#include <vector>

// Merge two sorted subarrays
std::vector<int> merge(const std::vector<int>& left, const std::vector<int>& right) {
    std::vector<int> result;
    size_t i = 0, j = 0;
    
    // Compare elements from both arrays and add smaller one to result
    while (i < left.size() && j < right.size()) {
        if (left[i] < right[j]) {
            result.push_back(left[i++]);
        } else {
            result.push_back(right[j++]);
        }
    }
    
    // Add any remaining elements
    while (i < left.size()) {
        result.push_back(left[i++]);
    }
    
    while (j < right.size()) {
        result.push_back(right[j++]);
    }
    
    return result;
}

std::vector<int> mergeSort(const std::vector<int>& arr) {
    // Base case: arrays with 0 or 1 element are already sorted
    if (arr.size() <= 1) {
        return arr;
    }
    
    // Split the array into two halves
    size_t middle = arr.size() / 2;
    std::vector<int> left(arr.begin(), arr.begin() + middle);
    std::vector<int> right(arr.begin() + middle, arr.end());
    
    // Recursively sort and merge the two halves
    return merge(mergeSort(left), mergeSort(right));
}

int main() {
    std::vector<int> array = {38, 27, 43, 3, 9, 82, 10};
    std::vector<int> sorted = mergeSort(array);
    
    // Print the sorted array
    for (const auto& num : sorted) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

Key Implementation Details:

• Recursive Design: Merge Sort is naturally implemented using recursion, where the base case is an array of size 0 or 1.
• Divide Step: The array is divided into roughly equal halves until reaching the base case.
• Merge Step: The core of the algorithm is the merge function, which combines two sorted arrays into a single sorted array.
• Auxiliary Space: Notice that merge sort creates new arrays in most implementations, using O(n) extra space.

Optimization Techniques:

• Insertion Sort for Small Arrays: For small subarrays (typically less than 10-20 elements), switching to insertion sort can improve performance.
• In-place Merge: Though more complex, in-place merging techniques can reduce the space complexity.
• Avoiding Redundant Copying: Using a pre-allocated auxiliary array that's reused throughout the sort can reduce overhead.
• Early Termination: If the last element of the left subarray is less than or equal to the first element of the right subarray, they're already in order and can be concatenated without merging.