Master Merge Sort - O(n log n) Algorithm

function mergeSort(arr) {
    /**
     * Merge Sort - Divide and Conquer Algorithm
     * Time: O(n log n) in all cases
     * Space: O(n) - auxiliary arrays
     */
    if (arr.length <= 1) return arr;

    // DIVIDE: Split array into two halves
    const mid = Math.floor(arr.length / 2);
    const left = mergeSort(arr.slice(0, mid));
    const right = mergeSort(arr.slice(mid));

    // CONQUER: Merge sorted halves
    return merge(left, right);
}

function merge(left, right) {
    const result = [];
    let i = 0, j = 0;

    // Compare and merge
    while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) {
            result.push(left[i++]);
        } else {
            result.push(right[j++]);
        }
    }

    // Append remaining elements
    return result.concat(left.slice(i), right.slice(j));
}

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

package main

import "fmt"

// MergeSort sorts an array using merge sort
// Time: O(n log n), Space: O(n)
func MergeSort(arr []int) []int {
    if len(arr) <= 1 {
        return arr
    }

    // DIVIDE: Split into two halves
    mid := len(arr) / 2
    left := MergeSort(arr[:mid])
    right := MergeSort(arr[mid:])

    // CONQUER: Merge sorted halves
    return merge(left, right)
}

func merge(left, right []int) []int {
    result := make([]int, 0, len(left)+len(right))
    i, j := 0, 0

    // Merge two sorted slices
    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++
        }
    }

    // Append remaining
    result = append(result, left[i:]...)
    result = append(result, right[j:]...)
    return result
}

func main() {
    arr := []int{38, 27, 43, 3, 9, 82, 10}
    sorted := MergeSort(arr)
    fmt.Println(sorted) // [3 9 10 27 38 43 82]
}

public class MergeSort {
    /**
     * Merge Sort - O(n log n) guaranteed
     * Space: O(n) auxiliary arrays
     */
    public static int[] mergeSort(int[] arr) {
        if (arr.length <= 1) return arr;

        // DIVIDE: Split into halves
        int mid = arr.length / 2;
        int[] left = new int[mid];
        int[] right = new int[arr.length - mid];

        System.arraycopy(arr, 0, left, 0, mid);
        System.arraycopy(arr, mid, right, 0, arr.length - mid);

        // Recursive sort
        left = mergeSort(left);
        right = mergeSort(right);

        // CONQUER: Merge
        return merge(left, right);
    }

    private static int[] merge(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];
        int i = 0, j = 0, k = 0;

        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) {
                result[k++] = left[i++];
            } else {
                result[k++] = right[j++];
            }
        }

        while (i < left.length) result[k++] = left[i++];
        while (j < right.length) result[k++] = right[j++];

        return result;
    }

    public static void main(String[] args) {
        int[] arr = {38, 27, 43, 3, 9, 82, 10};
        int[] sorted = mergeSort(arr);
        System.out.println(Arrays.toString(sorted));
    }
}

#include <vector>
#include <iostream>

// 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;

    while (i < left.size() && j < right.size()) {
        if (left[i] <= right[j]) {
            result.push_back(left[i++]);
        } else {
            result.push_back(right[j++]);
        }
    }

    result.insert(result.end(), left.begin() + i, left.end());
    result.insert(result.end(), right.begin() + j, right.end());
    return result;
}

// Merge Sort - O(n log n) guaranteed
std::vector<int> mergeSort(const std::vector<int>& arr) {
    if (arr.size() <= 1) return arr;

    // DIVIDE
    size_t mid = arr.size() / 2;
    std::vector<int> left(arr.begin(), arr.begin() + mid);
    std::vector<int> right(arr.begin() + mid, arr.end());

    // Recursive sort
    left = mergeSort(left);
    right = mergeSort(right);

    // CONQUER
    return merge(left, right);
}

int main() {
    std::vector<int> arr = {38, 27, 43, 3, 9, 82, 10};
    auto sorted = mergeSort(arr);

    for (int x : sorted) std::cout << x << " ";
    return 0;
}