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