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}

1DECLARE nums : ARRAY[1:7] OF INTEGER2DECLARE n : INTEGER3n ← 74nums[1] ← 75nums[2] ← 36nums[3] ← 97nums[4] ← 18nums[5] ← 59nums[6] ← 810nums[7] ← 211DECLARE temp : ARRAY[1:7] OF INTEGER12DECLARE i : INTEGER13
14PROCEDURE merge(lo : INTEGER, mid : INTEGER, hi : INTEGER)15    DECLARE a : INTEGER16    DECLARE b : INTEGER17    DECLARE k : INTEGER18    a ← lo19    b ← mid + 120    k ← lo21    WHILE a <= mid AND b <= hi DO22        IF nums[a] <= nums[b] THEN23            temp[k] ← nums[a]24            a ← a + 125        ELSE26            temp[k] ← nums[b]27            b ← b + 128        ENDIF29        k ← k + 130    ENDWHILE31    WHILE a <= mid DO32        temp[k] ← nums[a]33        a ← a + 134        k ← k + 135    ENDWHILE36    WHILE b <= hi DO37        temp[k] ← nums[b]38        b ← b + 139        k ← k + 140    ENDWHILE41    FOR k ← lo TO hi42        nums[k] ← temp[k]43    NEXT k44ENDPROCEDURE45
46PROCEDURE mergeSort(lo : INTEGER, hi : INTEGER)47    DECLARE mid : INTEGER48    IF lo < hi THEN49        mid ← (lo + hi) DIV 250        // Sort each half, then merge them51        CALL mergeSort(lo, mid)52        CALL mergeSort(mid + 1, hi)53        CALL merge(lo, mid, hi)54    ENDIF55ENDPROCEDURE56
57CALL mergeSort(1, n)58
59FOR i ← 1 TO n60    OUTPUT nums[i]61NEXT i