AntInLoop

Merge Sort Algorithm Code Implementations

Complete Merge Sort Algorithm code implementations in C++, Python, Java, and JavaScript with time and space complexity analysis on AntInLoop.

Read Merge Sort Algorithm Guide ยท Launch Interactive Visualizer

C++ Implementation

// Merge Sort Implementation in C++
#include <iostream>
#include <vector>
#include <algorithm>

class MergeSort {
public:
    static std::vector<int> mergeSort(const std::vector<int>& arr) {
        if (arr.size() <= 1) {
            return arr;
        }
        
        std::vector<int> sortedArray = arr;
        mergeSortInPlace(sortedArray, 0, sortedArray.size() - 1);
        return sortedArray;
    }
    
private:
    static void mergeSortInPlace(std::vector<int>& arr, int left, int right) {
        if (left < right) {
            int mid = left + (right - left) / 2;
            mergeSortInPlace(arr, left, mid);
            mergeSortInPlace(arr, mid + 1, right);
            merge(arr, left, mid, right);
        }
    }
    
    static void merge(std::vector<int>& arr, int left, int mid, int right) {
        // Create temporary arrays
        int leftSize = mid - left + 1;
        int rightSize = right - mid;
        
        std::vector<int> leftArray(leftSize);
        std::vector<int> rightArray(rightSize);
        
        // Copy data to temporary arrays
        for (int i = 0; i < leftSize; i++) {
            leftArray[i] = arr[left + i];
        }
        for (int j = 0; j < rightSize; j++) {
            rightArray[j] = arr[mid + 1 + j];
        }
        
        // Merge the temporary arrays back into arr
        int leftIndex = 0;
        int rightIndex = 0;
        int currentIndex = left;
        
        while (leftIndex < leftSize && rightIndex < rightSize) {
            if (leftArray[leftIndex] <= rightArray[rightIndex]) {
                arr[currentIndex] = leftArray[leftIndex];
                leftIndex++;
            } else {
                arr[currentIndex] = rightArray[rightIndex];
                rightIndex++;
            }
            currentIndex++;
        }
        
        // Copy remaining elements from leftArray
        while (leftIndex < leftSize) {
            arr[currentIndex] = leftArray[leftIndex];
            leftIndex++;
            currentIndex++;
        }
        
        // Copy remaining elements from rightArray
        while (rightIndex < rightSize) {
            arr[currentIndex] = rightArray[rightIndex];
            rightIndex++;
            currentIndex++;
        }
    }
    
public:
    // Alternative implementation with separate merge method
    static std::vector<int> mergeSortSeparate(const std::vector<int>& arr) {
        if (arr.size() <= 1) {
            return arr;
        }
        
        int mid = arr.size() / 2;
        std::vector<int> left(arr.begin(), arr.begin() + mid);
        std::vector<int> right(arr.begin() + mid, arr.end());
        
        // Recursively sort left and right arrays
        left = mergeSortSeparate(left);
        right = mergeSortSeparate(right);
        
        // Merge the sorted arrays
        return mergeArrays(left, right);
    }
    
private:
    static std::vector<int> mergeArrays(const std::vector<int>& left, const std::vector<int>& right) {
        std::vector<int> result;
        result.reserve(left.size() + right.size());
        
        int leftIndex = 0;
        int rightIndex = 0;
        
        while (leftIndex < left.size() && rightIndex < right.size()) {
            if (left[leftIndex] <= right[rightIndex]) {
                result.push_back(left[leftIndex]);
                leftIndex++;
            } else {
                result.push_back(right[rightIndex]);
                rightIndex++;
            }
        }
        
        // Copy remaining elements from left array
        while (leftIndex < left.size()) {
            result.push_back(left[leftIndex]);
            leftIndex++;
        }
        
        // Copy remaining elements from right array
        while (rightIndex < right.size()) {
            result.push_back(right[rightIndex]);
            rightIndex++;
        }
        
        return result;
    }
};

JAVA Implementation

// Merge Sort Implementation in Java
public class MergeSort {
    public static int[] mergeSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return arr.clone();
        }
        
        int[] sortedArray = arr.clone();
        mergeSortInPlace(sortedArray, 0, sortedArray.length - 1);
        return sortedArray;
    }
    
    private static void mergeSortInPlace(int[] arr, int left, int right) {
        if (left < right) {
            int mid = left + (right - left) / 2;
            mergeSortInPlace(arr, left, mid);
            mergeSortInPlace(arr, mid + 1, right);
            merge(arr, left, mid, right);
        }
    }
    
    private static void merge(int[] arr, int left, int mid, int right) {
        // Create temporary arrays
        int leftSize = mid - left + 1;
        int rightSize = right - mid;
        
        int[] leftArray = new int[leftSize];
        int[] rightArray = new int[rightSize];
        
        // Copy data to temporary arrays
        for (int i = 0; i < leftSize; i++) {
            leftArray[i] = arr[left + i];
        }
        for (int j = 0; j < rightSize; j++) {
            rightArray[j] = arr[mid + 1 + j];
        }
        
        // Merge the temporary arrays back into arr
        int leftIndex = 0;
        int rightIndex = 0;
        int currentIndex = left;
        
        while (leftIndex < leftSize && rightIndex < rightSize) {
            if (leftArray[leftIndex] <= rightArray[rightIndex]) {
                arr[currentIndex] = leftArray[leftIndex];
                leftIndex++;
            } else {
                arr[currentIndex] = rightArray[rightIndex];
                rightIndex++;
            }
            currentIndex++;
        }
        
        // Copy remaining elements from leftArray
        while (leftIndex < leftSize) {
            arr[currentIndex] = leftArray[leftIndex];
            leftIndex++;
            currentIndex++;
        }
        
        // Copy remaining elements from rightArray
        while (rightIndex < rightSize) {
            arr[currentIndex] = rightArray[rightIndex];
            rightIndex++;
            currentIndex++;
        }
    }
    
    // Alternative implementation with separate merge method
    public static int[] mergeSortSeparate(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return arr.clone();
        }
        
        int mid = arr.length / 2;
        int[] left = new int[mid];
        int[] right = new int[arr.length - mid];
        
        // Copy elements to left and right arrays
        for (int i = 0; i < mid; i++) {
            left[i] = arr[i];
        }
        for (int i = mid; i < arr.length; i++) {
            right[i - mid] = arr[i];
        }
        
        // Recursively sort left and right arrays
        left = mergeSortSeparate(left);
        right = mergeSortSeparate(right);
        
        // Merge the sorted arrays
        return mergeArrays(left, right);
    }
    
    private static int[] mergeArrays(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];
        int leftIndex = 0;
        int rightIndex = 0;
        int resultIndex = 0;
        
        while (leftIndex < left.length && rightIndex < right.length) {
            if (left[leftIndex] <= right[rightIndex]) {
                result[resultIndex] = left[leftIndex];
                leftIndex++;
            } else {
                result[resultIndex] = right[rightIndex];
                rightIndex++;
            }
            resultIndex++;
        }
        
        // Copy remaining elements from left array
        while (leftIndex < left.length) {
            result[resultIndex] = left[leftIndex];
            leftIndex++;
            resultIndex++;
        }
        
        // Copy remaining elements from right array
        while (rightIndex < right.length) {
            result[resultIndex] = right[rightIndex];
            rightIndex++;
            resultIndex++;
        }
        
        return result;
    }
}

JAVASCRIPT Implementation

// Merge Sort Implementation in JavaScript
function mergeSort(arr) {
  // Base case: arrays with 0 or 1 element are already sorted
  if (arr.length <= 1) {
    return arr;
  }
  
  // Divide: split array into two halves
  const mid = Math.floor(arr.length / 2);
  const left = arr.slice(0, mid);
  const right = arr.slice(mid);
  
  // Conquer: recursively sort the two halves
  const sortedLeft = mergeSort(left);
  const sortedRight = mergeSort(right);
  
  // Combine: merge the sorted halves
  return merge(sortedLeft, sortedRight);
}

function merge(left, right) {
  const result = [];
  let leftIndex = 0;
  let rightIndex = 0;
  
  // Compare elements from both arrays and merge in sorted order
  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] <= right[rightIndex]) {
      result.push(left[leftIndex]);
      leftIndex++;
    } else {
      result.push(right[rightIndex]);
      rightIndex++;
    }
  }
  
  // Add remaining elements from left array
  while (leftIndex < left.length) {
    result.push(left[leftIndex]);
    leftIndex++;
  }
  
  // Add remaining elements from right array
  while (rightIndex < right.length) {
    result.push(right[rightIndex]);
    rightIndex++;
  }
  
  return result;
}

// In-place Merge Sort implementation (more memory efficient)
function mergeSortInPlace(arr, left = 0, right = arr.length - 1) {
  if (left < right) {
    const mid = Math.floor((left + right) / 2);
    mergeSortInPlace(arr, left, mid);
    mergeSortInPlace(arr, mid + 1, right);
    mergeInPlace(arr, left, mid, right);
  }
  return arr;
}

function mergeInPlace(arr, left, mid, right) {
  const leftArray = arr.slice(left, mid + 1);
  const rightArray = arr.slice(mid + 1, right + 1);
  
  let leftIndex = 0;
  let rightIndex = 0;
  let currentIndex = left;
  
  while (leftIndex < leftArray.length && rightIndex < rightArray.length) {
    if (leftArray[leftIndex] <= rightArray[rightIndex]) {
      arr[currentIndex] = leftArray[leftIndex];
      leftIndex++;
    } else {
      arr[currentIndex] = rightArray[rightIndex];
      rightIndex++;
    }
    currentIndex++;
  }
  
  // Copy remaining elements from left array
  while (leftIndex < leftArray.length) {
    arr[currentIndex] = leftArray[leftIndex];
    leftIndex++;
    currentIndex++;
  }
  
  // Copy remaining elements from right array
  while (rightIndex < rightArray.length) {
    arr[currentIndex] = rightArray[rightIndex];
    rightIndex++;
    currentIndex++;
  }
}

PYTHON Implementation

# Merge Sort Implementation in Python
def merge_sort(arr):
    # Base case: arrays with 0 or 1 element are already sorted
    if len(arr) <= 1:
        return arr
    
    # Divide: split array into two halves
    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]
    
    # Conquer: recursively sort the two halves
    sorted_left = merge_sort(left)
    sorted_right = merge_sort(right)
    
    # Combine: merge the sorted halves
    return merge(sorted_left, sorted_right)

def merge(left, right):
    result = []
    left_index = 0
    right_index = 0
    
    # Compare elements from both arrays and merge in sorted order
    while left_index < len(left) and right_index < len(right):
        if left[left_index] <= right[right_index]:
            result.append(left[left_index])
            left_index += 1
        else:
            result.append(right[right_index])
            right_index += 1
    
    # Add remaining elements from left array
    result.extend(left[left_index:])
    
    # Add remaining elements from right array
    result.extend(right[right_index:])
    
    return result

# In-place Merge Sort implementation (more memory efficient)
def merge_sort_in_place(arr, left=0, right=None):
    if right is None:
        right = len(arr) - 1
    
    if left < right:
        mid = (left + right) // 2
        merge_sort_in_place(arr, left, mid)
        merge_sort_in_place(arr, mid + 1, right)
        merge_in_place(arr, left, mid, right)
    
    return arr

def merge_in_place(arr, left, mid, right):
    left_array = arr[left:mid + 1]
    right_array = arr[mid + 1:right + 1]
    
    left_index = 0
    right_index = 0
    current_index = left
    
    while left_index < len(left_array) and right_index < len(right_array):
        if left_array[left_index] <= right_array[right_index]:
            arr[current_index] = left_array[left_index]
            left_index += 1
        else:
            arr[current_index] = right_array[right_index]
            right_index += 1
        current_index += 1
    
    # Copy remaining elements from left array
    while left_index < len(left_array):
        arr[current_index] = left_array[left_index]
        left_index += 1
        current_index += 1
    
    # Copy remaining elements from right array
    while right_index < len(right_array):
        arr[current_index] = right_array[right_index]
        right_index += 1
        current_index += 1