Merge Sort

Given an array of integers, your task is to sort the array in ascending order using the Merge Sort algorithm.

Merge Sort is a divide and conquer algorithm. It divides the array into halves, recursively sorts them, and then merges the sorted halves into one final sorted array.

This algorithm is stable and guarantees a worst-case time complexity of O(n log n).

Understanding the Problem

Imagine you have a messy list of numbers — like cards scattered on a table — and your goal is to sort them in increasing order. The problem we’re solving is: How can we sort an array efficiently?

One powerful way to do this is by using an algorithm called Merge Sort. It doesn't sort the whole thing in one go. Instead, it breaks the array into smaller parts, sorts those, and then puts them back together — all in the right order!

Our Strategy: Divide and Conquer

Merge Sort uses a classic strategy called Divide and Conquer. That means:

1. First, divide the array into halves.
2. Then, recursively sort each half.
3. Finally, merge the sorted halves into a single sorted array.

Step-by-Step Example

Let’s go through a clear example to see how Merge Sort works in action.

Input: [4, 2, 7, 1]

Step 1: Divide the array into two halves → [4, 2] and [7, 1]

Step 2: Break those down further → [4], [2], [7], [1]

Now we have individual elements, and by definition, each single-element array is already sorted.

Step 3: Merge them back in sorted order:

• [4] and [2] → merge into [2, 4]
• [7] and [1] → merge into [1, 7]

Step 4: Merge [2, 4] and [1, 7] → final result: [1, 2, 4, 7]

Exploring Different Edge Cases

Case 1: Already Sorted Array

[1, 2, 3, 4] is already sorted. Merge Sort will still divide and merge, but it won’t need to do much actual rearranging.

Case 2: All Elements Are the Same

Input: [5, 5, 5, 5] → Output: [5, 5, 5, 5]

Merge Sort keeps the original order, which is known as stability.

Case 3: Single Element

Input: [10] → Already sorted, nothing to do.

Case 4: Empty Array

Input: [] → No elements to sort, so the output is also [].

Case 5: Negative Numbers

Merge Sort handles all numbers just fine, even if they’re negative.

Example: [5, -2, 0] → [-2, 0, 5]

Why Merge Sort Is a Great Choice

Merge Sort always takes O(n log n) time — even in the worst case — which is very efficient for large datasets. Plus, because it's a stable sort, it's perfect when the relative order of equal elements matters (like sorting records by multiple criteria).

1. Divide the unsorted array into n subarrays, each containing one element.
2. Repeatedly merge subarrays to produce new sorted subarrays until there is only one subarray remaining.
3. The final subarray is the sorted array.

#include <stdio.h>
#include <stdlib.h>

void merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;
    int *L = (int*) malloc(n1 * sizeof(int));
    int *R = (int*) malloc(n2 * sizeof(int));
    for (int i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];
    int i = 0, j = 0, k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k++] = L[i++];
        } else {
            arr[k++] = R[j++];
        }
    }
    while (i < n1)
        arr[k++] = L[i++];
    while (j < n2)
        arr[k++] = R[j++];
    free(L);
    free(R);
}

void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
        merge(arr, l, m, r);
    }
}

int main() {
    int arr[] = {6, 3, 8, 2, 7, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    mergeSort(arr, 0, n - 1);
    printf("Sorted array is: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

#include <iostream>
#include <vector>
using namespace std;

void merge(vector<int>& arr, int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;
    vector<int> L(n1), R(n2);
    for (int i = 0; i < n1; i++) {
        L[i] = arr[l + i];
    }
    for (int j = 0; j < n2; j++) {
        R[j] = arr[m + 1 + j];
    }
    int i = 0, j = 0, k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k++] = L[i++];
        } else {
            arr[k++] = R[j++];
        }
    }
    while (i < n1) {
        arr[k++] = L[i++];
    }
    while (j < n2) {
        arr[k++] = R[j++];
    }
}

void mergeSort(vector<int>& arr, int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
        merge(arr, l, m, r);
    }
}

int main() {
    vector<int> arr = {6, 3, 8, 2, 7, 4};
    mergeSort(arr, 0, arr.size() - 1);
    cout << "Sorted array is: ";
    for (int num : arr) {
        cout << num << " ";
    }
    return 0;
}

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    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
    result.extend(left[i:])
    result.extend(right[j:])
    return result

if __name__ == '__main__':
    arr = [6, 3, 8, 2, 7, 4]
    sorted_arr = merge_sort(arr)
    print("Sorted array is:", sorted_arr)

public class MergeSort {
    public static void mergeSort(int[] arr, int l, int r) {
        if (l < r) {
            int m = l + (r - l) / 2;
            mergeSort(arr, l, m);
            mergeSort(arr, m + 1, r);
            merge(arr, l, m, r);
        }
    }

    public static void merge(int[] arr, int l, int m, int r) {
        int n1 = m - l + 1;
        int n2 = r - m;
        int[] L = new int[n1];
        int[] R = new int[n2];
        for (int i = 0; i < n1; i++) {
            L[i] = arr[l + i];
        }
        for (int j = 0; j < n2; j++) {
            R[j] = arr[m + 1 + j];
        }
        int i = 0, j = 0, k = l;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k++] = L[i++];
            } else {
                arr[k++] = R[j++];
            }
        }
        while (i < n1) {
            arr[k++] = L[i++];
        }
        while (j < n2) {
            arr[k++] = R[j++];
        }
    }

    public static void main(String[] args) {
        int[] arr = {6, 3, 8, 2, 7, 4};
        mergeSort(arr, 0, arr.length - 1);
        System.out.print("Sorted array is: ");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

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

function merge(left, right) {
    let result = [];
    while (left.length && right.length) {
        if (left[0] <= right[0]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }
    return result.concat(left, right);
}

let arr = [6, 3, 8, 2, 7, 4];
arr = mergeSort(arr);
console.log("Sorted array is:", arr);

package main
import "fmt"

func merge(left, right []int) []int {
    var result []int
    i, j := 0, 0
    for i < len(left) && j < len(right) {
        if left[i] <= right[j] {
            result = append(result, left[i])
            i++
        } else {
            result = append(result, right[j])
            j++
        }
    }
    result = append(result, left[i:]...)
    result = append(result, right[j:]...)
    return result
}

func mergeSort(arr []int) []int {
    if len(arr) <= 1 {
        return arr
    }
    mid := len(arr) / 2
    left := mergeSort(arr[:mid])
    right := mergeSort(arr[mid:])
    return merge(left, right)
}

func main() {
    arr := []int{6, 3, 8, 2, 7, 4}
    sorted := mergeSort(arr)
    fmt.Println("Sorted array is:", sorted)
}

fn merge_sort(mut arr: Vec<i32>) -> Vec<i32> {
    if arr.len() <= 1 {
        return arr;
    }
    let mid = arr.len() / 2;
    let left = merge_sort(arr[..mid].to_vec());
    let right = merge_sort(arr[mid..].to_vec());
    merge(left, right)
}

fn merge(left: Vec<i32>, right: Vec<i32>) -> Vec<i32> {
    let mut result = Vec::new();
    let mut i = 0;
    let mut j = 0;
    while i < left.len() && j < right.len() {
        if left[i] <= right[j] {
            result.push(left[i]);
            i += 1;
        } else {
            result.push(right[j]);
            j += 1;
        }
    }
    result.extend_from_slice(&left[i..]);
    result.extend_from_slice(&right[j..]);
    result
}

fn main() {
    let arr = vec![6, 3, 8, 2, 7, 4];
    let sorted = merge_sort(arr);
    println!("Sorted array is: {:?}", sorted);
}

fun mergeSort(arr: IntArray): IntArray {
    if (arr.size <= 1) return arr
    val mid = arr.size / 2
    val left = mergeSort(arr.sliceArray(0 until mid))
    val right = mergeSort(arr.sliceArray(mid until arr.size))
    return merge(left, right)
}

fun merge(left: IntArray, right: IntArray): IntArray {
    var i = 0
    var j = 0
    val merged = mutableListOf<Int>()
    while (i < left.size && j < right.size) {
        if (left[i] <= right[j]) {
            merged.add(left[i])
            i++
        } else {
            merged.add(right[j])
            j++
        }
    }
    while (i < left.size) {
        merged.add(left[i])
        i++
    }
    while (j < right.size) {
        merged.add(right[j])
        j++
    }
    return merged.toIntArray()
}

fun main() {
    val arr = intArrayOf(6, 3, 8, 2, 7, 4)
    val sorted = mergeSort(arr)
    println("Sorted array is: " + sorted.joinToString(" "))
}

func mergeSort(_ arr: [Int]) -> [Int] {
    guard arr.count > 1 else { return arr }
    let mid = arr.count / 2
    let left = mergeSort(Array(arr[0..<mid]))
    let right = mergeSort(Array(arr[mid..<arr.count]))
    return merge(left, right)
}

func merge(_ left: [Int], _ right: [Int]) -> [Int] {
    var merged: [Int] = []
    var i = 0, j = 0
    while i < left.count && j < right.count {
        if left[i] <= right[j] {
            merged.append(left[i])
            i += 1
        } else {
            merged.append(right[j])
            j += 1
        }
    }
    while i < left.count {
        merged.append(left[i])
        i += 1
    }
    while j < right.count {
        merged.append(right[j])
        j += 1
    }
    return merged
}

var arr = [6, 3, 8, 2, 7, 4]
arr = mergeSort(arr)
print("Sorted array is:", arr)

function mergeSort(arr: number[]): number[] {
    if (arr.length <= 1) {
        return arr;
    }
    const mid = Math.floor(arr.length / 2);
    const left = mergeSort(arr.slice(0, mid));
    const right = mergeSort(arr.slice(mid));
    return merge(left, right);
}

function merge(left: number[], right: number[]): number[] {
    let result: number[] = [];
    let i = 0, j = 0;
    while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) {
            result.push(left[i++]);
        } else {
            result.push(right[j++]);
        }
    }
    return result.concat(left.slice(i)).concat(right.slice(j));
}

const arr = [6, 3, 8, 2, 7, 4];
const sorted = mergeSort(arr);
console.log("Sorted array is:", sorted);

Time complexity

Space complexity

O(n)

Merge Sort requires additional space to store temporary subarrays during the merge process. This auxiliary space grows linearly with the input size.