Merge Sort

1def merge_sort(a):2    if len(a) <= 1:3        return a4    mid = len(a) // 25    left = merge_sort(a[:mid])6    right = merge_sort(a[mid:])7    return merge(left, right)8
9
10def merge(left, right):11    out = []12    i = j = 013    while i < len(left) and j < len(right):14        if left[i] <= right[j]:15            out.append(left[i])16            i += 117        else:18            out.append(right[j])19            j += 120    out.extend(left[i:])21    out.extend(right[j:])22    return out23
24
25nums = [38, 27, 43, 3, 9, 82, 10]26print("Before:", nums)27print("After: ", merge_sort(nums))

1function mergeSort(arr) {2    if (arr.length <= 1) return arr;3    const mid = Math.floor(arr.length / 2);4    const left = mergeSort(arr.slice(0, mid));5    const right = mergeSort(arr.slice(mid));6    return merge(left, right);7}8
9// Merge two sorted arrays into one sorted array10function merge(left, right) {11    const out = [];12    let i = 0;13    let j = 0;14    while (i < left.length && j < right.length) {15        out.push(left[i] <= right[j] ? left[i++] : right[j++]);16    }17    return out.concat(left.slice(i), right.slice(j));18}19
20const data = [5, 2, 9, 1, 7, 3];21console.log("Before:", data);22console.log("Sorted:", mergeSort(data));

1import java.util.Arrays;2
3public class Main {4    static void mergeSort(int[] arr, int left, int right) {5        if (left >= right) return;6        int mid = (left + right) / 2;7        mergeSort(arr, left, mid);8        mergeSort(arr, mid + 1, right);9        merge(arr, left, mid, right);10    }11
12    // Merge two sorted halves into a temp array, then copy back13    static void merge(int[] arr, int left, int mid, int right) {14        int[] tmp = new int[right - left + 1];15        int i = left, j = mid + 1, k = 0;16        while (i <= mid && j <= right) {17            tmp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];18        }19        while (i <= mid) tmp[k++] = arr[i++];20        while (j <= right) tmp[k++] = arr[j++];21        System.arraycopy(tmp, 0, arr, left, tmp.length);22    }23
24    public static void main(String[] args) {25        int[] arr = {38, 27, 43, 3, 9, 82, 10};26        System.out.println("Before: " + Arrays.toString(arr));27        mergeSort(arr, 0, arr.length - 1);28        System.out.println("After:  " + Arrays.toString(arr));29    }30}

1#include <iostream>2#include <vector>3
4void printVec(const std::vector<int>& a) {5    for (int x : a) std::cout << x << " ";6    std::cout << "\n";7}8
9void merge(std::vector<int>& a, int lo, int mid, int hi) {10    std::vector<int> tmp;11    tmp.reserve(hi - lo + 1);12    int i = lo, j = mid + 1;13    while (i <= mid && j <= hi) {14        if (a[i] <= a[j]) tmp.push_back(a[i++]);15        else tmp.push_back(a[j++]);16    }17    while (i <= mid) tmp.push_back(a[i++]);18    while (j <= hi) tmp.push_back(a[j++]);19    for (size_t k = 0; k < tmp.size(); ++k) a[lo + k] = tmp[k];20}21
22void mergeSort(std::vector<int>& a, int lo, int hi) {23    if (lo >= hi) return;24    int mid = lo + (hi - lo) / 2;25    mergeSort(a, lo, mid);      // sort the left half26    mergeSort(a, mid + 1, hi);  // sort the right half27    merge(a, lo, mid, hi);      // merge the sorted halves28}29
30int main() {31    std::vector<int> data = {38, 27, 43, 3, 9, 82, 10};32    std::cout << "Before: ";33    printVec(data);34    mergeSort(data, 0, static_cast<int>(data.size()) - 1);35    std::cout << "After:  ";36    printVec(data);37    return 0;38}

1#include <stdio.h>2#include <stdlib.h>3
4void printArr(const int a[], int n) {5    for (int i = 0; i < n; i++) printf("%d ", a[i]);6    printf("\n");7}8
9void merge(int a[], int lo, int mid, int hi) {10    int* tmp = malloc((hi - lo + 1) * sizeof(int));11    int i = lo, j = mid + 1, k = 0;12    while (i <= mid && j <= hi) {13        if (a[i] <= a[j]) tmp[k++] = a[i++];14        else tmp[k++] = a[j++];15    }16    while (i <= mid) tmp[k++] = a[i++];17    while (j <= hi) tmp[k++] = a[j++];18    for (k = 0; k <= hi - lo; k++) a[lo + k] = tmp[k];19    free(tmp);20}21
22void mergeSort(int a[], int lo, int hi) {23    if (lo >= hi) return;24    int mid = lo + (hi - lo) / 2;25    mergeSort(a, lo, mid);      // sort the left half26    mergeSort(a, mid + 1, hi);  // sort the right half27    merge(a, lo, mid, hi);      // merge the sorted halves28}29
30int main(void) {31    int data[] = {38, 27, 43, 3, 9, 82, 10};32    int n = sizeof(data) / sizeof(data[0]);33    printf("Before: ");34    printArr(data, n);35    mergeSort(data, 0, n - 1);36    printf("After:  ");37    printArr(data, n);38    return 0;39}