merge sort recursive java code example

Example 1: how to write a merge sort array method ni java

public static void mergeSort(int[] a, int n) {
    if (n < 2) {
        return;
    }
    int mid = n / 2;
    int[] l = new int[mid];
    int[] r = new int[n - mid];
 
    for (int i = 0; i < mid; i++) {
        l[i] = a[i];
    }
    for (int i = mid; i < n; i++) {
        r[i - mid] = a[i];
    }
    mergeSort(l, mid);
    mergeSort(r, n - mid);
 
    merge(a, l, r, mid, n - mid);
}

Example 2: how to write a merge sort array method ni java

public static void merge(
  int[] a, int[] l, int[] r, int left, int right) {
  
    int i = 0, j = 0, k = 0;
    while (i < left && j < right) {
        if (l[i] <= r[j]) {
            a[k++] = l[i++];
        }
        else {
            a[k++] = r[j++];
        }
    }
    while (i < left) {
        a[k++] = l[i++];
    }
    while (j < right) {
        a[k++] = r[j++];
    }
}

Example 3: merge sort

// @see https://www.youtube.com/watch?v=es2T6KY45cA&vl=en
// @see https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html

function merge(list, start, midpoint, end) {
    const left = list.slice(start, midpoint);
    const right = list.slice(midpoint, end);
    for (let topLeft = 0, topRight = 0, i = start; i < end; i += 1) {
        if (topLeft >= left.length) {
            list[i] = right[topRight++];
        } else if (topRight >= right.length) {
            list[i] = left[topLeft++];
        } else if (left[topLeft] < right[topRight]) {
            list[i] = left[topLeft++];
        } else {
            list[i] = right[topRight++];
        }
    }
}

function mergesort(list, start = 0, end = undefined) {
    if (end === undefined) {
        end = list.length;
    }
    if (end - start > 1) {
        const midpoint = ((end + start) / 2) >> 0;
        mergesort(list, start, midpoint);
        mergesort(list, midpoint, end);
        merge(list, start, midpoint, end);
    }
    return list;
}

mergesort([4, 7, 2, 6, 4, 1, 8, 3]);

Tags:

Java Example