Common Algorithms

Merge Sort

Merge sort divides an array into smaller pieces, sorts those pieces, and merges the sorted pieces back together. The divide-and-conquer structure gives predictable O(n log n) performance.

Basic Implementation

Basic.java
Replay: real traced execution (multi-file project)
import java.util.Arrays;

public class Basic {
    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = left + (right - left) / 2;
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);
            merge(arr, left, mid, right);
        }
    }
    public static void merge(int[] arr, int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;
        int[] leftArr = new int[n1];
        int[] rightArr = new int[n2];
        for (int i = 0; i < n1; i++)
            leftArr[i] = arr[left + i];
        for (int j = 0; j < n2; j++)
            rightArr[j] = arr[mid + 1 + j];
        int i = 0, j = 0, k = left;
        while (i < n1 && j < n2) {
            if (leftArr[i] <= rightArr[j]) {
                arr[k++] = leftArr[i++];
            } else {
                arr[k++] = rightArr[j++];
            }
        }
        while (i < n1) arr[k++] = leftArr[i++];
        while (j < n2) arr[k++] = rightArr[j++];
    }
    public static void main(String[] args) {
        int[] numbers = {38, 27, 43, 3, 9, 82, 10};

        System.out.println("Before: " + Arrays.toString(numbers));
        mergeSort(numbers, 0, numbers.length - 1);
        System.out.println("After:  " + Arrays.toString(numbers));
    }
}

  1. public static void main(String[] args)

    31}32public static void main(String[] args) {33    int[] numbers = {38, 27, 43, 3, 9, 82, 10};3435    System.out.println("Before: " + Arrays.toString(numbers));36    mergeSort(numbers, 0, numbers.length7 - 1);37    System.out.println("After:  " + Arrays.toString(numbers));
    outputBefore: [38, 27, 43, 3, 9, 82, 10]

  2. public static void mergeSort(int[] arr, int left, int right)

    pass 1 of 13
    3public class Basic {4    public static void mergeSort(int[] arr, int left0, int right6) {5        if (left < right) {
    13 passes — pass 1 is the card above
    passleftrightmid
    106—
    203—
    301—
    4000
    5110
    623—
    7222
    8332
    946—
    ⋯ 2 more passes ⋯
    12554
    13665

  3. mid ← 3

    pass 1 of 6
    4public static void mergeSort(int[] arr, int left, int right) {5    if (left0 < right6) {6        int mid→ 3 = left0 + (right6 - left) / 2;7        mergeSort(arr, left0, mid3);8        mergeSort(arr, mid + 1, right);
    All 6 passes — pass 1 is the card above
    passleftrightmid
    1063
    2031
    3010
    4232
    5465
    6454

  4. n1 ← 1, n2 ← 1

    pass 1 of 6
    11}12public static void merge(int[] arr, int left0, int mid0, int right1) {13    int n1→ 1 = mid0 - left0 + 1;14    int n2→ 1 = right1 - mid0;15    int[] leftArr = new int[n1];16    int[] rightArr = new int[n2];17    for (int i = 0; i < n1; i++)
    All 6 passes — pass 1 is the card above
    passleftmidrightn1n2
    100111
    222311
    301322
    444511
    545621
    603643

  5. leftArr[i] ← 38

    pass 1 of 11
    16int[] rightArr = new int[n2];17for (int i0 = 0; i < n11; i++)18    leftArr[i]→ 38 = arr[left + i]38;19for (int j = 0; j < n2; j++)
    All 11 passes — pass 1 is the card above
    passin1arr[left + i]leftleftArr[i]
    1013800 → 38
    2014320 → 43
    3022700 → 27
    4123800 → 38
    501940 → 9
    602940 → 9
    7128240 → 82
    804300 → 3
    9142700 → 27
    10243800 → 38
    11344300 → 43

  6. rightArr[j] ← 27

    pass 1 of 9
    18    leftArr[i] = arr[left + i];19for (int j0 = 0; j < n21; j++)20    rightArr[j]→ 27 = arr[mid + 1 + j]27;21int i = 0, j = 0, k = left;
    All 9 passes — pass 1 is the card above
    passjn2arr[mid + 1 + j]midrightArr[j]
    1012700 → 27
    201320 → 3
    302310 → 3
    4124310 → 43
    5018240 → 82
    6011050 → 10
    703930 → 9
    8131030 → 10
    9238230 → 82

  7. k ← 0

    20    rightArr[j] = arr[mid + 1 + j];21int i = 0, j = 0, k→ 0 = left;22while (i < n1 && j < n2) {

  8. while (i < n1 && j < n2)

    pass 1 of 14
    21int i = 0, j = 0, k = left;22while (i0 < n11 && j0 < n21) {23    if (leftArr[i] <= rightArr[j]) {
    14 passes — pass 1 is the card above
    passin1jn2
    10101
    20101
    30202
    40212
    51212
    60101
    70201
    81201
    90403
    ⋯ 3 more passes ⋯
    132423
    143423

  9. k ← 1, j ← 1

    pass 1 of 6
    24    arr[k++] = leftArr[i++];25} else {26    arr[k→ 1++] = rightArr[j→ 1++];27}
    All 6 passes — pass 1 is the card above
    passkj
    10 → 10 → 1
    22 → 30 → 1
    30 → 10 → 1
    45 → 60 → 1
    51 → 20 → 1
    62 → 31 → 2

  10. k ← 2, i ← 1, left ← 0, mid ← 1

    pass 1 of 3
    6        int mid = left + (right - left) / 2;7        mergeSort(arr, left→ 0, mid→ 1);8        mergeSort(arr, mid1 + 1, right3);9        merge(arr, left0, mid0, right1);10    }11}12public static void merge(int[] arr, int left, int mid, int right) {13    int n1 = mid - left + 1;14    int n2 = right - mid;15    int[] leftArr = new int[n1];16    int[] rightArr = new int[n2];17    for (int i = 0; i < n1; i++)18        leftArr[i] = arr[left + i];19    for (int j = 0; j < n2; j++)20        rightArr[j] = arr[mid + 1 + j];21    int i = 0, j = 0, k = left;22    while (i < n1 && j < n2) {23        if (leftArr[i] <= rightArr[j]) {24            arr[k++] = leftArr[i++];25        } else {26            arr[k++] = rightArr[j++];27        }28    }29    while (i0 < n11) arr[k→ 2++] = leftArr[i++];30    while (j < n2) arr[k++] = rightArr[j++];
    All 3 passes — pass 1 is the card above
    passn1kileftmidright
    111 → 20 → 100 → 11
    213 → 40 → 1013
    326 → 71 → 2036

  11. k ← 2

    20    rightArr[j] = arr[mid + 1 + j];21int i = 0, j = 0, k→ 2 = left;22while (i < n1 && j < n2) {

  12. k ← 0

    20    rightArr[j] = arr[mid + 1 + j];21int i = 0, j = 0, k→ 0 = left;22while (i < n1 && j < n2) {

  13. k ← 2, i ← 1

    pass 1 of 8
    22while (i < n1 && j < n2) {23    if (leftArr[i]27 <= rightArr[j]43) {24        arr[k→ 2++] = leftArr[i→ 1++];25    } else {
    All 8 passes — pass 1 is the card above
    passleftArr[i]rightArr[j]jki
    1274311 → 20 → 1
    2384312 → 31 → 2
    398204 → 50 → 1
    491004 → 50 → 1
    53900 → 10 → 1
    6278223 → 41 → 2
    7388224 → 52 → 3
    8438225 → 63 → 4

  14. k ← 4, j ← 2, left ← 0, mid ← 3

    pass 1 of 3
    6        int mid = left + (right - left) / 2;7        mergeSort(arr, left→ 0, mid→ 3);8        mergeSort(arr, mid3 + 1, right6);9        merge(arr, left0, mid1, right3);10    }11}12public static void merge(int[] arr, int left, int mid, int right) {13    int n1 = mid - left + 1;14    int n2 = right - mid;15    int[] leftArr = new int[n1];16    int[] rightArr = new int[n2];17    for (int i = 0; i < n1; i++)18        leftArr[i] = arr[left + i];19    for (int j = 0; j < n2; j++)20        rightArr[j] = arr[mid + 1 + j];21    int i = 0, j = 0, k = left;22    while (i < n1 && j < n2) {23        if (leftArr[i] <= rightArr[j]) {24            arr[k++] = leftArr[i++];25        } else {26            arr[k++] = rightArr[j++];27        }28    }29    while (i < n1) arr[k++] = leftArr[i++];30    while (j1 < n22) arr[k→ 4++] = rightArr[j++];31}
    All 3 passes — pass 1 is the card above
    passn2rightkjleftmid
    1233 → 41 → 201 → 3
    2155 → 60 → 144 → 5
    3366 → 72 → 303

  15. k ← 4

    20    rightArr[j] = arr[mid + 1 + j];21int i = 0, j = 0, k→ 4 = left;22while (i < n1 && j < n2) {

  16. k ← 4

    20    rightArr[j] = arr[mid + 1 + j];21int i = 0, j = 0, k→ 4 = left;22while (i < n1 && j < n2) {

  17. k ← 0

    20    rightArr[j] = arr[mid + 1 + j];21int i = 0, j = 0, k→ 0 = left;22while (i < n1 && j < n2) {

  18. mergeSort(numbers, 0, numbers.length - 1);

    35    System.out.println("Before: " + Arrays.toString(numbers));36    mergeSort(numbers, 0, numbers.length7 - 1);37    System.out.println("After:  " + Arrays.toString(numbers));38}
    outputAfter:  [3, 9, 10, 27, 38, 43, 82]
Divide and Conquer A problem-solving strategy that breaks a problem into smaller subproblems, solves them independently, and combines the results.

Tracing the Algorithm

The trace shows the recursive divide phase followed by the merge phase.

numbers
Trace.java
Replay: real traced execution (multi-file project)
import java.util.Arrays;

public class Trace {

    private static int depth = 0;
    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            indent();
            System.out.println("Divide: " + arrayRange(arr, left, right));
            depth++;

            int mid = left + (right - left) / 2;

            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);

            merge(arr, left, mid, right);

            depth--;
            indent();
            System.out.println("Merged: " + arrayRange(arr, left, right));
        }
    }
    public static void merge(int[] arr, int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;
        int[] leftArr = new int[n1];
        int[] rightArr = new int[n2];

        for (int i = 0; i < n1; i++)
            leftArr[i] = arr[left + i];
        for (int j = 0; j < n2; j++)
            rightArr[j] = arr[mid + 1 + j];

        indent();
        System.out.println("  Merge " + Arrays.toString(leftArr) +
                           " and " + Arrays.toString(rightArr));

        int i = 0, j = 0, k = left;
        while (i < n1 && j < n2) {
            if (leftArr[i] <= rightArr[j]) {
                arr[k++] = leftArr[i++];
            } else {
                arr[k++] = rightArr[j++];
            }
        }

        while (i < n1) arr[k++] = leftArr[i++];
        while (j < n2) arr[k++] = rightArr[j++];
    }

    private static void indent() {
        for (int i = 0; i < depth; i++) System.out.print("  ");
    }

    private static String arrayRange(int[] arr, int left, int right) {
        int[] range = new int[right - left + 1];
        for (int i = 0; i < range.length; i++)
            range[i] = arr[left + i];
        return Arrays.toString(range);
    }
    public static void main(String[] args) {
        int[] numbers = {5, 2, 8, 1, 9};

        System.out.println("Initial: " + Arrays.toString(numbers));
        System.out.println();
        mergeSort(numbers, 0, numbers.length - 1);
        System.out.println();
        System.out.println("Final:   " + Arrays.toString(numbers));
    }
}

import java.util.Arrays;

public class Trace {

    private static int depth = 0;
    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            indent();
            System.out.println("Divide: " + arrayRange(arr, left, right));
            depth++;

            int mid = left + (right - left) / 2;

            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);

            merge(arr, left, mid, right);

            depth--;
            indent();
            System.out.println("Merged: " + arrayRange(arr, left, right));
        }
    }
    public static void merge(int[] arr, int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;
        int[] leftArr = new int[n1];
        int[] rightArr = new int[n2];

        for (int i = 0; i < n1; i++)
            leftArr[i] = arr[left + i];
        for (int j = 0; j < n2; j++)
            rightArr[j] = arr[mid + 1 + j];

        indent();
        System.out.println("  Merge " + Arrays.toString(leftArr) +
                           " and " + Arrays.toString(rightArr));

        int i = 0, j = 0, k = left;
        while (i < n1 && j < n2) {
            if (leftArr[i] <= rightArr[j]) {
                arr[k++] = leftArr[i++];
            } else {
                arr[k++] = rightArr[j++];
            }
        }

        while (i < n1) arr[k++] = leftArr[i++];
        while (j < n2) arr[k++] = rightArr[j++];
    }

    private static void indent() {
        for (int i = 0; i < depth; i++) System.out.print("  ");
    }

    private static String arrayRange(int[] arr, int left, int right) {
        int[] range = new int[right - left + 1];
        for (int i = 0; i < range.length; i++)
            range[i] = arr[left + i];
        return Arrays.toString(range);
    }
    public static void main(String[] args) {
        int[] numbers = {4, 1, 3, 2};

        System.out.println("Initial: " + Arrays.toString(numbers));
        System.out.println();
        mergeSort(numbers, 0, numbers.length - 1);
        System.out.println();
        System.out.println("Final:   " + Arrays.toString(numbers));
    }
}

import java.util.Arrays;

public class Trace {

    private static int depth = 0;
    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            indent();
            System.out.println("Divide: " + arrayRange(arr, left, right));
            depth++;

            int mid = left + (right - left) / 2;

            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);

            merge(arr, left, mid, right);

            depth--;
            indent();
            System.out.println("Merged: " + arrayRange(arr, left, right));
        }
    }
    public static void merge(int[] arr, int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;
        int[] leftArr = new int[n1];
        int[] rightArr = new int[n2];

        for (int i = 0; i < n1; i++)
            leftArr[i] = arr[left + i];
        for (int j = 0; j < n2; j++)
            rightArr[j] = arr[mid + 1 + j];

        indent();
        System.out.println("  Merge " + Arrays.toString(leftArr) +
                           " and " + Arrays.toString(rightArr));

        int i = 0, j = 0, k = left;
        while (i < n1 && j < n2) {
            if (leftArr[i] <= rightArr[j]) {
                arr[k++] = leftArr[i++];
            } else {
                arr[k++] = rightArr[j++];
            }
        }

        while (i < n1) arr[k++] = leftArr[i++];
        while (j < n2) arr[k++] = rightArr[j++];
    }

    private static void indent() {
        for (int i = 0; i < depth; i++) System.out.print("  ");
    }

    private static String arrayRange(int[] arr, int left, int right) {
        int[] range = new int[right - left + 1];
        for (int i = 0; i < range.length; i++)
            range[i] = arr[left + i];
        return Arrays.toString(range);
    }
    public static void main(String[] args) {
        int[] numbers = {9, 7, 5, 3, 1};

        System.out.println("Initial: " + Arrays.toString(numbers));
        System.out.println();
        mergeSort(numbers, 0, numbers.length - 1);
        System.out.println();
        System.out.println("Final:   " + Arrays.toString(numbers));
    }
}

  1. public static void main(String[] args)

    61}62public static void main(String[] args) {63    int[] numbers = {5, 2, 8, 1, 9}; //@numbers={5, 2, 8, 1, 9}, {4, 1, 3, 2}, {9, 7, 5, 3, 1}6465    System.out.println("Initial: " + Arrays.toString(numbers));66    System.out.println();67    mergeSort(numbers, 0, numbers.length5 - 1);68    System.out.println();
    outputInitial: [5, 2, 8, 1, 9]

  2. public static void mergeSort(int[] arr, int left, int right)

    pass 1 of 9
    5private static int depth = 0;6public static void mergeSort(int[] arr, int left0, int right4) {7    if (left < right) {
    All 9 passes — pass 1 is the card above
    passleftrightmid
    104—
    202—
    301—
    4000
    5110
    6221
    734—
    8333
    9443

  3. if (left < right)

    pass 1 of 4
    6public static void mergeSort(int[] arr, int left, int right) {7    if (left0 < right4) {8        indent();9        System.out.println("Divide: " + arrayRange(arr, left, right));
    All 4 passes — pass 1 is the card above
    passleftright
    104
    202
    301
    434

  4. private static void indent()

    pass 1 of 12
    7    if (left < right) {8        indent();9        System.out.println("Divide: " + arrayRange(arr, left0, right4));10        depth++;1112        int mid = left + (right - left) / 2;1314        mergeSort(arr, left, mid);15        mergeSort(arr, mid + 1, right);1617        merge(arr, left, mid, right);1819        depth--;20        indent();21        System.out.println("Merged: " + arrayRange(arr, left, right));22    }23}24public static void merge(int[] arr, int left, int mid, int right) {25    int n1 = mid - left + 1;26    int n2 = right - mid;27    int[] leftArr = new int[n1];28    int[] rightArr = new int[n2];2930    for (int i = 0; i < n1; i++)31        leftArr[i] = arr[left + i];32    for (int j = 0; j < n2; j++)33        rightArr[j] = arr[mid + 1 + j];3435    indent();36    System.out.println("  Merge " + Arrays.toString(leftArr) + 37                       " and " + Arrays.toString(rightArr));3839    int i = 0, j = 0, k = left;40    while (i < n1 && j < n2) {41        if (leftArr[i] <= rightArr[j]) {42            arr[k++] = leftArr[i++];43        } else {44            arr[k++] = rightArr[j++];45        }46    }4748    while (i < n1) arr[k++] = leftArr[i++];49    while (j < n2) arr[k++] = rightArr[j++];50}5152private static void indent() {53    for (int i = 0; i < depth; i++) System.out.print("  ");
    All 12 passes — pass 1 is the card above
    passleftrightn1midkjidepth
    104——————
    2————————
    3————————
    401100 → 10 → 10 → 13 → 2
    5————————
    6————————
    7————————
    8————————
    9————————
    10————————
    11————0 → 10 → 1——
    1204——————

  5. private static String arrayRange(int[] arr, int left, int right)

    pass 1 of 8
    56private static String arrayRange(int[] arr, int left0, int right4) {57    int[] range = new int[right4 - left0 + 1];58    for (int i = 0; i < range.length; i++)
    All 8 passes — pass 1 is the card above
    passleftright
    104
    202
    301
    401
    502
    634
    734
    804

  6. range[i] ← 5

    pass 1 of 24
    57int[] range = new int[right - left + 1];58for (int i0 = 0; i < range.length5; i++)59    range[i]→ 5 = arr[left + i]5;60return Arrays.toString(range);
    24 passes — pass 1 is the card above
    passirange.lengtharr[left + i]leftrange[i]
    105500 → 5
    215200 → 2
    325800 → 8
    435100 → 1
    545900 → 9
    603500 → 5
    713200 → 2
    823800 → 8
    902500 → 5
    ⋯ 13 more passes ⋯
    2335800 → 8
    2445900 → 9

  7. return Arrays.toString(range);

    59        range[i] = arr[left + i];60    return Arrays.toString(range);61}

  8. depth ← 1, mid ← 2

    8indent();9System.out.println("Divide: " + arrayRange(arr, left0, right4));10depth→ 1++;1112int mid→ 2 = left0 + (right4 - left) / 2;1314mergeSort(arr, left0, mid2);15mergeSort(arr, mid + 1, right);
    outputDivide: [5, 2, 8, 1, 9]

  9. for (int i = 0; i < depth; i++)

    pass 1 of 16
    7    if (left < right) {8        indent();9        System.out.println("Divide: " + arrayRange(arr, left0, right2));10        depth++;1112        int mid = left + (right - left) / 2;1314        mergeSort(arr, left, mid);15        mergeSort(arr, mid + 1, right);1617        merge(arr, left, mid, right);1819        depth--;20        indent();21        System.out.println("Merged: " + arrayRange(arr, left, right));22    }23}24public static void merge(int[] arr, int left, int mid, int right) {25    int n1 = mid - left + 1;26    int n2 = right - mid;27    int[] leftArr = new int[n1];28    int[] rightArr = new int[n2];2930    for (int i = 0; i < n1; i++)31        leftArr[i] = arr[left + i];32    for (int j = 0; j < n2; j++)33        rightArr[j] = arr[mid + 1 + j];3435    indent();36    System.out.println("  Merge " + Arrays.toString(leftArr) + 37                       " and " + Arrays.toString(rightArr));3839    int i = 0, j = 0, k = left;40    while (i < n1 && j < n2) {41        if (leftArr[i] <= rightArr[j]) {42            arr[k++] = leftArr[i++];43        } else {44            arr[k++] = rightArr[j++];45        }46    }4748    while (i < n1) arr[k++] = leftArr[i++];49    while (j < n2) arr[k++] = rightArr[j++];50}5152private static void indent() {53    for (int i0 = 0; i < depth1; i++) System.out.print("  ");54}
    output
    16 passes — pass 1 is the card above
    passleftrightn1midkjidepth
    102————01
    2——————02
    301————12
    4——————03
    5——————13
    6011000 → 10 → 13 → 2
    7——————02
    801————12
    9——————02
    ⋯ 5 more passes ⋯
    1534————01
    16————00 → 101

  10. return Arrays.toString(range);

    59        range[i] = arr[left + i];60    return Arrays.toString(range);61}

  11. depth ← 2, mid ← 1

    8indent();9System.out.println("Divide: " + arrayRange(arr, left0, right2));10depth→ 2++;1112int mid→ 1 = left0 + (right2 - left) / 2;1314mergeSort(arr, left0, mid1);15mergeSort(arr, mid + 1, right);
    outputDivide: [5, 2, 8]

  12. return Arrays.toString(range);

    59        range[i] = arr[left + i];60    return Arrays.toString(range);61}

  13. depth ← 3, mid ← 0

    8indent();9System.out.println("Divide: " + arrayRange(arr, left0, right1));10depth→ 3++;1112int mid→ 0 = left0 + (right1 - left) / 2;1314mergeSort(arr, left0, mid0);15mergeSort(arr, mid + 1, right);
    outputDivide: [5, 2]

  14. n1 ← 1, n2 ← 1

    pass 1 of 4
    23}24public static void merge(int[] arr, int left0, int mid0, int right1) {25    int n1→ 1 = mid0 - left0 + 1;26    int n2→ 1 = right1 - mid0;27    int[] leftArr = new int[n1];28    int[] rightArr = new int[n2];
    All 4 passes — pass 1 is the card above
    passleftmidrightn1n2
    100111
    201221
    333411
    402432

  15. leftArr[i] ← 5

    pass 1 of 7
    30for (int i0 = 0; i < n11; i++)31    leftArr[i]→ 5 = arr[left + i]5;32for (int j = 0; j < n2; j++)
    All 7 passes — pass 1 is the card above
    passin1arr[left + i]leftleftArr[i]
    101500 → 5
    202200 → 2
    312500 → 5
    401130 → 1
    503200 → 2
    613500 → 5
    723800 → 8

  16. rightArr[j] ← 2

    pass 1 of 5
    31    leftArr[i] = arr[left + i];32for (int j0 = 0; j < n21; j++)33    rightArr[j]→ 2 = arr[mid + 1 + j]2;
    All 5 passes — pass 1 is the card above
    passjn2arr[mid + 1 + j]midrightArr[j]
    101200 → 2
    201810 → 8
    301930 → 9
    402120 → 1
    512920 → 9

  17. indent();

    35indent();36System.out.println("  Merge " + Arrays.toString(leftArr) +

  18. while (i < n1 && j < n2)

    pass 1 of 8
    39int i = 0, j = 0, k = left;40while (i0 < n11 && j0 < n21) {41    if (leftArr[i] <= rightArr[j]) {
    All 8 passes — pass 1 is the card above
    passn1n2leftmidrightkjidepth
    1110010 → 10 → 10 → 13 → 2
    221————00—
    321————01—
    411————00—
    532———0 → 10 → 10—
    632————10—
    732————11—
    832————12—

  19. k ← 1, j ← 1

    pass 1 of 2
    42    arr[k++] = leftArr[i++];43} else {44    arr[k→ 1++] = rightArr[j→ 1++];45}

  20. k ← 2, i ← 1, depth ← 2

    17        merge(arr, left0, mid0, right1);1819        depth→ 2--;20        indent();21        System.out.println("Merged: " + arrayRange(arr, left, right));22    }23}24public static void merge(int[] arr, int left, int mid, int right) {25    int n1 = mid - left + 1;26    int n2 = right - mid;27    int[] leftArr = new int[n1];28    int[] rightArr = new int[n2];2930    for (int i = 0; i < n1; i++)31        leftArr[i] = arr[left + i];32    for (int j = 0; j < n2; j++)33        rightArr[j] = arr[mid + 1 + j];3435    indent();36    System.out.println("  Merge " + Arrays.toString(leftArr) + 37                       " and " + Arrays.toString(rightArr));3839    int i = 0, j = 0, k = left;40    while (i < n1 && j < n2) {41        if (leftArr[i] <= rightArr[j]) {42            arr[k++] = leftArr[i++];43        } else {44            arr[k++] = rightArr[j++];45        }46    }4748    while (i0 < n11) arr[k→ 2++] = leftArr[i++];49    while (j < n2) arr[k++] = rightArr[j++];

  21. return Arrays.toString(range);

    59        range[i] = arr[left + i];60    return Arrays.toString(range);61}

  22. left ← 0, mid ← 1

    14    mergeSort(arr, left→ 0, mid→ 1);15    mergeSort(arr, mid1 + 1, right2);1617    merge(arr, left, mid, right);1819    depth--;20    indent();21    System.out.println("Merged: " + arrayRange(arr, left0, right1));22}
    outputMerged: [2, 5]

  23. indent();

    35indent();36System.out.println("  Merge " + Arrays.toString(leftArr) +

  24. k ← 1, i ← 1

    pass 1 of 6
    40while (i < n1 && j < n2) {41    if (leftArr[i]2 <= rightArr[j]8) {42        arr[k→ 1++] = leftArr[i→ 1++];43    } else {
    All 6 passes — pass 1 is the card above
    passleftArr[i]rightArr[j]jki
    12800 → 10 → 1
    25801 → 21 → 2
    31903 → 40 → 1
    42911 → 20 → 1
    55912 → 31 → 2
    68913 → 42 → 3

  25. k ← 3, j ← 1, depth ← 1

    pass 1 of 3
    17        merge(arr, left0, mid1, right2);1819        depth→ 1--;20        indent();21        System.out.println("Merged: " + arrayRange(arr, left, right));22    }23}24public static void merge(int[] arr, int left, int mid, int right) {25    int n1 = mid - left + 1;26    int n2 = right - mid;27    int[] leftArr = new int[n1];28    int[] rightArr = new int[n2];2930    for (int i = 0; i < n1; i++)31        leftArr[i] = arr[left + i];32    for (int j = 0; j < n2; j++)33        rightArr[j] = arr[mid + 1 + j];3435    indent();36    System.out.println("  Merge " + Arrays.toString(leftArr) + 37                       " and " + Arrays.toString(rightArr));3839    int i = 0, j = 0, k = left;40    while (i < n1 && j < n2) {41        if (leftArr[i] <= rightArr[j]) {42            arr[k++] = leftArr[i++];43        } else {44            arr[k++] = rightArr[j++];45        }46    }4748    while (i < n1) arr[k++] = leftArr[i++];49    while (j0 < n21) arr[k→ 3++] = rightArr[j++];50}
    All 3 passes — pass 1 is the card above
    passn2leftmidrightkjdepth
    110122 → 30 → 12 → 1
    213344 → 50 → 12 → 1
    320244 → 51 → 21 → 0

  26. return Arrays.toString(range);

    59        range[i] = arr[left + i];60    return Arrays.toString(range);61}

  27. left ← 0, mid ← 2

    14    mergeSort(arr, left→ 0, mid→ 2);15    mergeSort(arr, mid2 + 1, right4);1617    merge(arr, left, mid, right);1819    depth--;20    indent();21    System.out.println("Merged: " + arrayRange(arr, left0, right2));22}
    outputMerged: [2, 5, 8]

  28. return Arrays.toString(range);

    59        range[i] = arr[left + i];60    return Arrays.toString(range);61}

  29. depth ← 2, mid ← 3

    8indent();9System.out.println("Divide: " + arrayRange(arr, left3, right4));10depth→ 2++;1112int mid→ 3 = left3 + (right4 - left) / 2;1314mergeSort(arr, left3, mid3);15mergeSort(arr, mid + 1, right);
    outputDivide: [1, 9]

  30. indent();

    35indent();36System.out.println("  Merge " + Arrays.toString(leftArr) +

  31. return Arrays.toString(range);

    59        range[i] = arr[left + i];60    return Arrays.toString(range);61}

  32. mid ← 2, right ← 4

    14    mergeSort(arr, left, mid);15    mergeSort(arr, mid→ 2 + 1, right→ 4);1617    merge(arr, left0, mid2, right4);1819    depth--;20    indent();21    System.out.println("Merged: " + arrayRange(arr, left3, right4));22}
    outputMerged: [1, 9]

  33. indent();

    35indent();36System.out.println("  Merge " + Arrays.toString(leftArr) +

  34. k ← 1, j ← 1

    pass 2 of 2
    42    arr[k++] = leftArr[i++];43} else {44    arr[k→ 1++] = rightArr[j→ 1++];45}

  35. return Arrays.toString(range);

    59        range[i] = arr[left + i];60    return Arrays.toString(range);61}

  36. System.out.println("Merged: " + arrayRange(arr, left, right));

    20        indent();21        System.out.println("Merged: " + arrayRange(arr, left0, right4));22    }23}24public static void merge(int[] arr, int left, int mid, int right) {25    int n1 = mid - left + 1;26    int n2 = right - mid;27    int[] leftArr = new int[n1];28    int[] rightArr = new int[n2];2930    for (int i = 0; i < n1; i++)31        leftArr[i] = arr[left + i];32    for (int j = 0; j < n2; j++)33        rightArr[j] = arr[mid + 1 + j];3435    indent();36    System.out.println("  Merge " + Arrays.toString(leftArr) + 37                       " and " + Arrays.toString(rightArr));3839    int i = 0, j = 0, k = left;40    while (i < n1 && j < n2) {41        if (leftArr[i] <= rightArr[j]) {42            arr[k++] = leftArr[i++];43        } else {44            arr[k++] = rightArr[j++];45        }46    }4748    while (i < n1) arr[k++] = leftArr[i++];49    while (j < n2) arr[k++] = rightArr[j++];50}5152private static void indent() {53    for (int i = 0; i < depth; i++) System.out.print("  ");54}5556private static String arrayRange(int[] arr, int left, int right) {57    int[] range = new int[right - left + 1];58    for (int i = 0; i < range.length; i++)59        range[i] = arr[left + i];60    return Arrays.toString(range);61}62public static void main(String[] args) {63    int[] numbers = {5, 2, 8, 1, 9}; //@numbers={5, 2, 8, 1, 9}, {4, 1, 3, 2}, {9, 7, 5, 3, 1}6465    System.out.println("Initial: " + Arrays.toString(numbers));66    System.out.println();67    mergeSort(numbers, 0, numbers.length5 - 1);68    System.out.println();69    System.out.println("Final:   " + Arrays.toString(numbers));70}
    outputMerged: [1, 2, 5, 8, 9]
Final:   [1, 2, 5, 8, 9]

  1. public static void main(String[] args)

    61}62public static void main(String[] args) {63    int[] numbers = {4, 1, 3, 2};6465    System.out.println("Initial: " + Arrays.toString(numbers));66    System.out.println();67    mergeSort(numbers, 0, numbers.length4 - 1);68    System.out.println();
    outputInitial: [4, 1, 3, 2]

  2. public static void mergeSort(int[] arr, int left, int right)

    pass 1 of 7
    5private static int depth = 0;6public static void mergeSort(int[] arr, int left0, int right3) {7    if (left < right) {
    All 7 passes — pass 1 is the card above
    passleftrightmid
    103—
    201—
    3000
    4110
    523—
    6222
    7332

  3. if (left < right)

    pass 1 of 3
    6public static void mergeSort(int[] arr, int left, int right) {7    if (left0 < right3) {8        indent();9        System.out.println("Divide: " + arrayRange(arr, left, right));
    All 3 passes — pass 1 is the card above
    passleftright
    103
    201
    323

  4. private static void indent()

    pass 1 of 9
    7    if (left < right) {8        indent();9        System.out.println("Divide: " + arrayRange(arr, left0, right3));10        depth++;1112        int mid = left + (right - left) / 2;1314        mergeSort(arr, left, mid);15        mergeSort(arr, mid + 1, right);1617        merge(arr, left, mid, right);1819        depth--;20        indent();21        System.out.println("Merged: " + arrayRange(arr, left, right));22    }23}24public static void merge(int[] arr, int left, int mid, int right) {25    int n1 = mid - left + 1;26    int n2 = right - mid;27    int[] leftArr = new int[n1];28    int[] rightArr = new int[n2];2930    for (int i = 0; i < n1; i++)31        leftArr[i] = arr[left + i];32    for (int j = 0; j < n2; j++)33        rightArr[j] = arr[mid + 1 + j];3435    indent();36    System.out.println("  Merge " + Arrays.toString(leftArr) + 37                       " and " + Arrays.toString(rightArr));3839    int i = 0, j = 0, k = left;40    while (i < n1 && j < n2) {41        if (leftArr[i] <= rightArr[j]) {42            arr[k++] = leftArr[i++];43        } else {44            arr[k++] = rightArr[j++];45        }46    }4748    while (i < n1) arr[k++] = leftArr[i++];49    while (j < n2) arr[k++] = rightArr[j++];50}5152private static void indent() {53    for (int i = 0; i < depth; i++) System.out.print("  ");
    All 9 passes — pass 1 is the card above
    passleftrightleftArr[i]rightArr[j]jki
    103—————
    2———————
    3———————
    4———————
    5———————
    6———————
    7———————
    8——1200 → 10 → 1
    903—————

  5. private static String arrayRange(int[] arr, int left, int right)

    pass 1 of 6
    56private static String arrayRange(int[] arr, int left0, int right3) {57    int[] range = new int[right3 - left0 + 1];58    for (int i = 0; i < range.length; i++)
    All 6 passes — pass 1 is the card above
    passleftright
    103
    201
    301
    423
    523
    603

  6. range[i] ← 4

    pass 1 of 16
    57int[] range = new int[right - left + 1];58for (int i0 = 0; i < range.length4; i++)59    range[i]→ 4 = arr[left + i]4;60return Arrays.toString(range);
    16 passes — pass 1 is the card above
    passirange.lengtharr[left + i]leftrange[i]
    104400 → 4
    214100 → 1
    324300 → 3
    434200 → 2
    502400 → 4
    612100 → 1
    702100 → 1
    812400 → 4
    902320 → 3
    ⋯ 5 more passes ⋯
    1524300 → 3
    1634400 → 4

  7. return Arrays.toString(range);

    59        range[i] = arr[left + i];60    return Arrays.toString(range);61}

  8. depth ← 1, mid ← 1

    8indent();9System.out.println("Divide: " + arrayRange(arr, left0, right3));10depth→ 1++;1112int mid→ 1 = left0 + (right3 - left) / 2;1314mergeSort(arr, left0, mid1);15mergeSort(arr, mid + 1, right);
    outputDivide: [4, 1, 3, 2]

  9. for (int i = 0; i < depth; i++)

    pass 1 of 9
    7    if (left < right) {8        indent();9        System.out.println("Divide: " + arrayRange(arr, left0, right1));10        depth++;1112        int mid = left + (right - left) / 2;1314        mergeSort(arr, left, mid);15        mergeSort(arr, mid + 1, right);1617        merge(arr, left, mid, right);1819        depth--;20        indent();21        System.out.println("Merged: " + arrayRange(arr, left, right));22    }23}24public static void merge(int[] arr, int left, int mid, int right) {25    int n1 = mid - left + 1;26    int n2 = right - mid;27    int[] leftArr = new int[n1];28    int[] rightArr = new int[n2];2930    for (int i = 0; i < n1; i++)31        leftArr[i] = arr[left + i];32    for (int j = 0; j < n2; j++)33        rightArr[j] = arr[mid + 1 + j];3435    indent();36    System.out.println("  Merge " + Arrays.toString(leftArr) + 37                       " and " + Arrays.toString(rightArr));3839    int i = 0, j = 0, k = left;40    while (i < n1 && j < n2) {41        if (leftArr[i] <= rightArr[j]) {42            arr[k++] = leftArr[i++];43        } else {44            arr[k++] = rightArr[j++];45        }46    }4748    while (i < n1) arr[k++] = leftArr[i++];49    while (j < n2) arr[k++] = rightArr[j++];50}5152private static void indent() {53    for (int i0 = 0; i < depth1; i++) System.out.print("  ");54}
    output
    All 9 passes — pass 1 is the card above
    passdepthleftrightleftArr[i]rightArr[j]jki
    1101————0
    22——————0
    32—————01
    4101————0
    5123————0
    62——————0
    72—————21
    8123————0
    91——12000 → 1

  10. return Arrays.toString(range);

    59        range[i] = arr[left + i];60    return Arrays.toString(range);61}

  11. depth ← 2, mid ← 0

    8indent();9System.out.println("Divide: " + arrayRange(arr, left0, right1));10depth→ 2++;1112int mid→ 0 = left0 + (right1 - left) / 2;1314mergeSort(arr, left0, mid0);15mergeSort(arr, mid + 1, right);
    outputDivide: [4, 1]

  12. n1 ← 1, n2 ← 1

    pass 1 of 3
    23}24public static void merge(int[] arr, int left0, int mid0, int right1) {25    int n1→ 1 = mid0 - left0 + 1;26    int n2→ 1 = right1 - mid0;27    int[] leftArr = new int[n1];28    int[] rightArr = new int[n2];
    All 3 passes — pass 1 is the card above
    passleftmidrightn1n2
    100111
    222311
    301322

  13. leftArr[i] ← 4

    pass 1 of 4
    30for (int i0 = 0; i < n11; i++)31    leftArr[i]→ 4 = arr[left + i]4;32for (int j = 0; j < n2; j++)
    All 4 passes — pass 1 is the card above
    passin1arr[left + i]leftleftArr[i]
    101400 → 4
    201320 → 3
    302100 → 1
    412400 → 4

  14. rightArr[j] ← 1

    pass 1 of 4
    31    leftArr[i] = arr[left + i];32for (int j0 = 0; j < n21; j++)33    rightArr[j]→ 1 = arr[mid + 1 + j]1;
    All 4 passes — pass 1 is the card above
    passjn2arr[mid + 1 + j]midrightArr[j]
    101100 → 1
    201220 → 2
    302210 → 2
    412310 → 3

  15. indent();

    35indent();36System.out.println("  Merge " + Arrays.toString(leftArr) +

  16. while (i < n1 && j < n2)

    pass 1 of 5
    39int i = 0, j = 0, k = left;40while (i0 < n11 && j0 < n21) {41    if (leftArr[i] <= rightArr[j]) {
    All 5 passes — pass 1 is the card above
    passn1jn2leftArr[i]rightArr[j]ki
    1101———0
    2101———0
    3202120 → 10 → 1
    4202———1
    5212———1

  17. k ← 1, j ← 1

    pass 1 of 4
    42    arr[k++] = leftArr[i++];43} else {44    arr[k→ 1++] = rightArr[j→ 1++];45}
    All 4 passes — pass 1 is the card above
    passkj
    10 → 10 → 1
    22 → 30 → 1
    31 → 20 → 1
    42 → 31 → 2

  18. k ← 2, i ← 1, depth ← 1

    pass 1 of 3
    17        merge(arr, left0, mid0, right1);1819        depth→ 1--;20        indent();21        System.out.println("Merged: " + arrayRange(arr, left, right));22    }23}24public static void merge(int[] arr, int left, int mid, int right) {25    int n1 = mid - left + 1;26    int n2 = right - mid;27    int[] leftArr = new int[n1];28    int[] rightArr = new int[n2];2930    for (int i = 0; i < n1; i++)31        leftArr[i] = arr[left + i];32    for (int j = 0; j < n2; j++)33        rightArr[j] = arr[mid + 1 + j];3435    indent();36    System.out.println("  Merge " + Arrays.toString(leftArr) + 37                       " and " + Arrays.toString(rightArr));3839    int i = 0, j = 0, k = left;40    while (i < n1 && j < n2) {41        if (leftArr[i] <= rightArr[j]) {42            arr[k++] = leftArr[i++];43        } else {44            arr[k++] = rightArr[j++];45        }46    }4748    while (i0 < n11) arr[k→ 2++] = leftArr[i++];49    while (j < n2) arr[k++] = rightArr[j++];
    All 3 passes — pass 1 is the card above
    passn1leftmidrightkidepth
    110011 → 20 → 12 → 1
    212233 → 40 → 12 → 1
    320133 → 41 → 21 → 0

  19. return Arrays.toString(range);

    59        range[i] = arr[left + i];60    return Arrays.toString(range);61}

  20. left ← 0, mid ← 1

    14    mergeSort(arr, left→ 0, mid→ 1);15    mergeSort(arr, mid1 + 1, right3);1617    merge(arr, left, mid, right);1819    depth--;20    indent();21    System.out.println("Merged: " + arrayRange(arr, left0, right1));22}
    outputMerged: [1, 4]

  21. return Arrays.toString(range);

    59        range[i] = arr[left + i];60    return Arrays.toString(range);61}

  22. depth ← 2, mid ← 2

    8indent();9System.out.println("Divide: " + arrayRange(arr, left2, right3));10depth→ 2++;1112int mid→ 2 = left2 + (right3 - left) / 2;1314mergeSort(arr, left2, mid2);15mergeSort(arr, mid + 1, right);
    outputDivide: [3, 2]

  23. indent();

    35indent();36System.out.println("  Merge " + Arrays.toString(leftArr) +

  24. return Arrays.toString(range);

    59        range[i] = arr[left + i];60    return Arrays.toString(range);61}

  25. mid ← 1, right ← 3

    14    mergeSort(arr, left, mid);15    mergeSort(arr, mid→ 1 + 1, right→ 3);1617    merge(arr, left0, mid1, right3);1819    depth--;20    indent();21    System.out.println("Merged: " + arrayRange(arr, left2, right3));22}
    outputMerged: [2, 3]

  26. indent();

    35indent();36System.out.println("  Merge " + Arrays.toString(leftArr) +

  27. k ← 1, i ← 1

    40while (i < n1 && j < n2) {41    if (leftArr[i]1 <= rightArr[j]2) {42        arr[k→ 1++] = leftArr[i→ 1++];43    } else {
    values this step0j

  28. return Arrays.toString(range);

    59        range[i] = arr[left + i];60    return Arrays.toString(range);61}

  29. System.out.println("Merged: " + arrayRange(arr, left, right));

    20        indent();21        System.out.println("Merged: " + arrayRange(arr, left0, right3));22    }23}24public static void merge(int[] arr, int left, int mid, int right) {25    int n1 = mid - left + 1;26    int n2 = right - mid;27    int[] leftArr = new int[n1];28    int[] rightArr = new int[n2];2930    for (int i = 0; i < n1; i++)31        leftArr[i] = arr[left + i];32    for (int j = 0; j < n2; j++)33        rightArr[j] = arr[mid + 1 + j];3435    indent();36    System.out.println("  Merge " + Arrays.toString(leftArr) + 37                       " and " + Arrays.toString(rightArr));3839    int i = 0, j = 0, k = left;40    while (i < n1 && j < n2) {41        if (leftArr[i] <= rightArr[j]) {42            arr[k++] = leftArr[i++];43        } else {44            arr[k++] = rightArr[j++];45        }46    }4748    while (i < n1) arr[k++] = leftArr[i++];49    while (j < n2) arr[k++] = rightArr[j++];50}5152private static void indent() {53    for (int i = 0; i < depth; i++) System.out.print("  ");54}5556private static String arrayRange(int[] arr, int left, int right) {57    int[] range = new int[right - left + 1];58    for (int i = 0; i < range.length; i++)59        range[i] = arr[left + i];60    return Arrays.toString(range);61}62public static void main(String[] args) {63    int[] numbers = {4, 1, 3, 2};6465    System.out.println("Initial: " + Arrays.toString(numbers));66    System.out.println();67    mergeSort(numbers, 0, numbers.length4 - 1);68    System.out.println();69    System.out.println("Final:   " + Arrays.toString(numbers));70}
    outputMerged: [1, 2, 3, 4]
Final:   [1, 2, 3, 4]

  1. public static void main(String[] args)

    61}62public static void main(String[] args) {63    int[] numbers = {9, 7, 5, 3, 1};6465    System.out.println("Initial: " + Arrays.toString(numbers));66    System.out.println();67    mergeSort(numbers, 0, numbers.length5 - 1);68    System.out.println();
    outputInitial: [9, 7, 5, 3, 1]

  2. public static void mergeSort(int[] arr, int left, int right)

    pass 1 of 9
    5private static int depth = 0;6public static void mergeSort(int[] arr, int left0, int right4) {7    if (left < right) {
    All 9 passes — pass 1 is the card above
    passleftrightmid
    104—
    202—
    301—
    4000
    5110
    6221
    734—
    8333
    9443

  3. if (left < right)

    pass 1 of 4
    6public static void mergeSort(int[] arr, int left, int right) {7    if (left0 < right4) {8        indent();9        System.out.println("Divide: " + arrayRange(arr, left, right));
    All 4 passes — pass 1 is the card above
    passleftright
    104
    202
    301
    434

  4. private static void indent()

    pass 1 of 12
    7    if (left < right) {8        indent();9        System.out.println("Divide: " + arrayRange(arr, left0, right4));10        depth++;1112        int mid = left + (right - left) / 2;1314        mergeSort(arr, left, mid);15        mergeSort(arr, mid + 1, right);1617        merge(arr, left, mid, right);1819        depth--;20        indent();21        System.out.println("Merged: " + arrayRange(arr, left, right));22    }23}24public static void merge(int[] arr, int left, int mid, int right) {25    int n1 = mid - left + 1;26    int n2 = right - mid;27    int[] leftArr = new int[n1];28    int[] rightArr = new int[n2];2930    for (int i = 0; i < n1; i++)31        leftArr[i] = arr[left + i];32    for (int j = 0; j < n2; j++)33        rightArr[j] = arr[mid + 1 + j];3435    indent();36    System.out.println("  Merge " + Arrays.toString(leftArr) + 37                       " and " + Arrays.toString(rightArr));3839    int i = 0, j = 0, k = left;40    while (i < n1 && j < n2) {41        if (leftArr[i] <= rightArr[j]) {42            arr[k++] = leftArr[i++];43        } else {44            arr[k++] = rightArr[j++];45        }46    }4748    while (i < n1) arr[k++] = leftArr[i++];49    while (j < n2) arr[k++] = rightArr[j++];50}5152private static void indent() {53    for (int i = 0; i < depth; i++) System.out.print("  ");
    All 12 passes — pass 1 is the card above
    passleftright
    104
    2——
    3——
    4——
    5——
    6——
    7——
    8——
    9——
    10——
    11——
    1204

  5. private static String arrayRange(int[] arr, int left, int right)

    pass 1 of 8
    56private static String arrayRange(int[] arr, int left0, int right4) {57    int[] range = new int[right4 - left0 + 1];58    for (int i = 0; i < range.length; i++)
    All 8 passes — pass 1 is the card above
    passleftright
    104
    202
    301
    401
    502
    634
    734
    804

  6. range[i] ← 9

    pass 1 of 24
    57int[] range = new int[right - left + 1];58for (int i0 = 0; i < range.length5; i++)59    range[i]→ 9 = arr[left + i]9;60return Arrays.toString(range);
    24 passes — pass 1 is the card above
    passirange.lengtharr[left + i]leftrange[i]
    105900 → 9
    215700 → 7
    325500 → 5
    435300 → 3
    545100 → 1
    603900 → 9
    713700 → 7
    823500 → 5
    902900 → 9
    ⋯ 13 more passes ⋯
    2335700 → 7
    2445900 → 9

  7. return Arrays.toString(range);

    59        range[i] = arr[left + i];60    return Arrays.toString(range);61}

  8. depth ← 1, mid ← 2

    8indent();9System.out.println("Divide: " + arrayRange(arr, left0, right4));10depth→ 1++;1112int mid→ 2 = left0 + (right4 - left) / 2;1314mergeSort(arr, left0, mid2);15mergeSort(arr, mid + 1, right);
    outputDivide: [9, 7, 5, 3, 1]

  9. for (int i = 0; i < depth; i++)

    pass 1 of 16
    7    if (left < right) {8        indent();9        System.out.println("Divide: " + arrayRange(arr, left0, right2));10        depth++;1112        int mid = left + (right - left) / 2;1314        mergeSort(arr, left, mid);15        mergeSort(arr, mid + 1, right);1617        merge(arr, left, mid, right);1819        depth--;20        indent();21        System.out.println("Merged: " + arrayRange(arr, left, right));22    }23}24public static void merge(int[] arr, int left, int mid, int right) {25    int n1 = mid - left + 1;26    int n2 = right - mid;27    int[] leftArr = new int[n1];28    int[] rightArr = new int[n2];2930    for (int i = 0; i < n1; i++)31        leftArr[i] = arr[left + i];32    for (int j = 0; j < n2; j++)33        rightArr[j] = arr[mid + 1 + j];3435    indent();36    System.out.println("  Merge " + Arrays.toString(leftArr) + 37                       " and " + Arrays.toString(rightArr));3839    int i = 0, j = 0, k = left;40    while (i < n1 && j < n2) {41        if (leftArr[i] <= rightArr[j]) {42            arr[k++] = leftArr[i++];43        } else {44            arr[k++] = rightArr[j++];45        }46    }4748    while (i < n1) arr[k++] = leftArr[i++];49    while (j < n2) arr[k++] = rightArr[j++];50}5152private static void indent() {53    for (int i0 = 0; i < depth1; i++) System.out.print("  ");54}
    output
    16 passes — pass 1 is the card above
    passidepthleftrightk
    10102—
    202———
    31201—
    403———
    513———
    623——0
    702———
    81201—
    902———
    ⋯ 5 more passes ⋯
    150134—
    1601——0

  10. return Arrays.toString(range);

    59        range[i] = arr[left + i];60    return Arrays.toString(range);61}

  11. depth ← 2, mid ← 1

    8indent();9System.out.println("Divide: " + arrayRange(arr, left0, right2));10depth→ 2++;1112int mid→ 1 = left0 + (right2 - left) / 2;1314mergeSort(arr, left0, mid1);15mergeSort(arr, mid + 1, right);
    outputDivide: [9, 7, 5]

  12. return Arrays.toString(range);

    59        range[i] = arr[left + i];60    return Arrays.toString(range);61}

  13. depth ← 3, mid ← 0

    8indent();9System.out.println("Divide: " + arrayRange(arr, left0, right1));10depth→ 3++;1112int mid→ 0 = left0 + (right1 - left) / 2;1314mergeSort(arr, left0, mid0);15mergeSort(arr, mid + 1, right);
    outputDivide: [9, 7]

  14. n1 ← 1, n2 ← 1

    pass 1 of 4
    23}24public static void merge(int[] arr, int left0, int mid0, int right1) {25    int n1→ 1 = mid0 - left0 + 1;26    int n2→ 1 = right1 - mid0;27    int[] leftArr = new int[n1];28    int[] rightArr = new int[n2];
    All 4 passes — pass 1 is the card above
    passleftmidrightn1n2
    100111
    201221
    333411
    402432

  15. leftArr[i] ← 9

    pass 1 of 7
    30for (int i0 = 0; i < n11; i++)31    leftArr[i]→ 9 = arr[left + i]9;32for (int j = 0; j < n2; j++)
    All 7 passes — pass 1 is the card above
    passin1arr[left + i]leftleftArr[i]
    101900 → 9
    202700 → 7
    312900 → 9
    401330 → 3
    503500 → 5
    613700 → 7
    723900 → 9

  16. rightArr[j] ← 7

    pass 1 of 5
    31    leftArr[i] = arr[left + i];32for (int j0 = 0; j < n21; j++)33    rightArr[j]→ 7 = arr[mid + 1 + j]7;
    All 5 passes — pass 1 is the card above
    passjn2arr[mid + 1 + j]midrightArr[j]
    101700 → 7
    201510 → 5
    301130 → 1
    402120 → 1
    512320 → 3

  17. indent();

    35indent();36System.out.println("  Merge " + Arrays.toString(leftArr) +

  18. while (i < n1 && j < n2)

    pass 1 of 5
    39int i = 0, j = 0, k = left;40while (i0 < n11 && j0 < n21) {41    if (leftArr[i] <= rightArr[j]) {
    All 5 passes — pass 1 is the card above
    passn1jn2
    1101
    2201
    3101
    4302
    5312

  19. k ← 1, j ← 1

    pass 1 of 5
    42    arr[k++] = leftArr[i++];43} else {44    arr[k→ 1++] = rightArr[j→ 1++];45}
    All 5 passes — pass 1 is the card above
    passkj
    10 → 10 → 1
    20 → 10 → 1
    33 → 40 → 1
    40 → 10 → 1
    51 → 21 → 2

  20. k ← 2, i ← 1, depth ← 2

    pass 1 of 7
    17        merge(arr, left0, mid0, right1);1819        depth→ 2--;20        indent();21        System.out.println("Merged: " + arrayRange(arr, left, right));22    }23}24public static void merge(int[] arr, int left, int mid, int right) {25    int n1 = mid - left + 1;26    int n2 = right - mid;27    int[] leftArr = new int[n1];28    int[] rightArr = new int[n2];2930    for (int i = 0; i < n1; i++)31        leftArr[i] = arr[left + i];32    for (int j = 0; j < n2; j++)33        rightArr[j] = arr[mid + 1 + j];3435    indent();36    System.out.println("  Merge " + Arrays.toString(leftArr) + 37                       " and " + Arrays.toString(rightArr));3839    int i = 0, j = 0, k = left;40    while (i < n1 && j < n2) {41        if (leftArr[i] <= rightArr[j]) {42            arr[k++] = leftArr[i++];43        } else {44            arr[k++] = rightArr[j++];45        }46    }4748    while (i0 < n11) arr[k→ 2++] = leftArr[i++];49    while (j < n2) arr[k++] = rightArr[j++];
    All 7 passes — pass 1 is the card above
    passn1leftmidrightkidepth
    110011 → 20 → 13 → 2
    22———1 → 20 → 1—
    320122 → 31 → 22 → 1
    413344 → 50 → 12 → 1
    53———2 → 30 → 1—
    63———3 → 41 → 2—
    730244 → 52 → 31 → 0

  21. return Arrays.toString(range);

    59        range[i] = arr[left + i];60    return Arrays.toString(range);61}

  22. left ← 0, mid ← 1

    14    mergeSort(arr, left→ 0, mid→ 1);15    mergeSort(arr, mid1 + 1, right2);1617    merge(arr, left, mid, right);1819    depth--;20    indent();21    System.out.println("Merged: " + arrayRange(arr, left0, right1));22}
    outputMerged: [7, 9]

  23. indent();

    35indent();36System.out.println("  Merge " + Arrays.toString(leftArr) +

  24. return Arrays.toString(range);

    59        range[i] = arr[left + i];60    return Arrays.toString(range);61}

  25. left ← 0, mid ← 2

    14    mergeSort(arr, left→ 0, mid→ 2);15    mergeSort(arr, mid2 + 1, right4);1617    merge(arr, left, mid, right);1819    depth--;20    indent();21    System.out.println("Merged: " + arrayRange(arr, left0, right2));22}
    outputMerged: [5, 7, 9]

  26. return Arrays.toString(range);

    59        range[i] = arr[left + i];60    return Arrays.toString(range);61}

  27. depth ← 2, mid ← 3

    8indent();9System.out.println("Divide: " + arrayRange(arr, left3, right4));10depth→ 2++;1112int mid→ 3 = left3 + (right4 - left) / 2;1314mergeSort(arr, left3, mid3);15mergeSort(arr, mid + 1, right);
    outputDivide: [3, 1]

  28. indent();

    35indent();36System.out.println("  Merge " + Arrays.toString(leftArr) +

  29. return Arrays.toString(range);

    59        range[i] = arr[left + i];60    return Arrays.toString(range);61}

  30. mid ← 2, right ← 4

    14    mergeSort(arr, left, mid);15    mergeSort(arr, mid→ 2 + 1, right→ 4);1617    merge(arr, left0, mid2, right4);1819    depth--;20    indent();21    System.out.println("Merged: " + arrayRange(arr, left3, right4));22}
    outputMerged: [1, 3]

  31. indent();

    35indent();36System.out.println("  Merge " + Arrays.toString(leftArr) +

  32. return Arrays.toString(range);

    59        range[i] = arr[left + i];60    return Arrays.toString(range);61}

  33. System.out.println("Merged: " + arrayRange(arr, left, right));

    20        indent();21        System.out.println("Merged: " + arrayRange(arr, left0, right4));22    }23}24public static void merge(int[] arr, int left, int mid, int right) {25    int n1 = mid - left + 1;26    int n2 = right - mid;27    int[] leftArr = new int[n1];28    int[] rightArr = new int[n2];2930    for (int i = 0; i < n1; i++)31        leftArr[i] = arr[left + i];32    for (int j = 0; j < n2; j++)33        rightArr[j] = arr[mid + 1 + j];3435    indent();36    System.out.println("  Merge " + Arrays.toString(leftArr) + 37                       " and " + Arrays.toString(rightArr));3839    int i = 0, j = 0, k = left;40    while (i < n1 && j < n2) {41        if (leftArr[i] <= rightArr[j]) {42            arr[k++] = leftArr[i++];43        } else {44            arr[k++] = rightArr[j++];45        }46    }4748    while (i < n1) arr[k++] = leftArr[i++];49    while (j < n2) arr[k++] = rightArr[j++];50}5152private static void indent() {53    for (int i = 0; i < depth; i++) System.out.print("  ");54}5556private static String arrayRange(int[] arr, int left, int right) {57    int[] range = new int[right - left + 1];58    for (int i = 0; i < range.length; i++)59        range[i] = arr[left + i];60    return Arrays.toString(range);61}62public static void main(String[] args) {63    int[] numbers = {9, 7, 5, 3, 1};6465    System.out.println("Initial: " + Arrays.toString(numbers));66    System.out.println();67    mergeSort(numbers, 0, numbers.length5 - 1);68    System.out.println();69    System.out.println("Final:   " + Arrays.toString(numbers));70}
    outputMerged: [1, 3, 5, 7, 9]
Final:   [1, 3, 5, 7, 9]

The Merge Operation

MergeOnly.java
Replay: real traced execution (multi-file project)
import java.util.Arrays;

public class MergeOnly {
    public static int[] mergeTwoSorted(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[] left = {1, 3, 5, 7};
        int[] right = {2, 4, 6, 8};

        System.out.println("Left:  " + Arrays.toString(left));
        System.out.println("Right: " + Arrays.toString(right));

        int[] merged = mergeTwoSorted(left, right);
        System.out.println("Merged: " + Arrays.toString(merged));
        int[] arr1 = {1, 5, 9};
        int[] arr2 = {2, 3, 4, 6, 7};

        System.out.println("\nLeft:  " + Arrays.toString(arr1));
        System.out.println("Right: " + Arrays.toString(arr2));

        int[] merged2 = mergeTwoSorted(arr1, arr2);
        System.out.println("Merged: " + Arrays.toString(merged2));
    }
}

  1. public static void main(String[] args)

    22}23public static void main(String[] args) {24    int[] left = {1, 3, 5, 7};25    int[] right = {2, 4, 6, 8};2627    System.out.println("Left:  " + Arrays.toString(left));28    System.out.println("Right: " + Arrays.toString(right));2930    int[] merged = mergeTwoSorted(left, right);31    System.out.println("Merged: " + Arrays.toString(merged));
    outputLeft:  [1, 3, 5, 7]
Right: [2, 4, 6, 8]

  2. k ← 0

    pass 1 of 2
    3public class MergeOnly {4    public static int[] mergeTwoSorted(int[] left, int[] right) {5        int[] result = new int[left.length4 + right.length4];6        int i = 0, j = 0, k→ 0 = 0;7        while (i < left.length && j < right.length) {

  3. while (i < left.length && j < right.length)

    pass 1 of 14
    6int i = 0, j = 0, k = 0;7while (i0 < left.length4 && j0 < right.length4) {8    if (left[i] <= right[j]) {
    14 passes — pass 1 is the card above
    passleft.lengthright.lengthkji
    144—00
    244—01
    344—11
    444—12
    544—22
    644—23
    7447 → 83 → 43
    835—00
    935—01
    ⋯ 3 more passes ⋯
    1335—32
    14357 → 842 → 3

  4. k ← 1, i ← 1

    pass 1 of 6
    7while (i < left.length && j < right.length) {8    if (left[i]1 <= right[j]2) {9        result[k→ 1++] = left[i→ 1++];10    } else {
    All 6 passes — pass 1 is the card above
    passleft[i]right[j]right.lengthleft.lengthkij
    112——0 → 10 → 10
    234——2 → 31 → 21
    356——4 → 52 → 32
    4784—6 → 73 → 43 → 4
    512——0 → 10 → 10
    656—34 → 51 → 23

  5. k ← 2, j ← 1

    pass 1 of 8
    9    result[k++] = left[i++];10} else {11    result[k→ 2++] = right[j→ 1++];12}
    All 8 passes — pass 1 is the card above
    passright.lengthleft.lengthkji
    1——1 → 20 → 1—
    2——3 → 41 → 2—
    34—5 → 62 → 3—
    4——1 → 20 → 1—
    5——2 → 31 → 2—
    6——3 → 42 → 3—
    7——5 → 63 → 4—
    8—36 → 74 → 52 → 3

  6. k ← 8, j ← 4

    16}17while (j3 < right.length4) {18    result[k→ 8++] = right[j→ 4++];19}

  7. return result;

    21    return result;22}

  8. int[] merged = mergeTwoSorted(left, right);

    30int[] merged = mergeTwoSorted(left, right);31System.out.println("Merged: " + Arrays.toString(merged));32int[] arr1 = {1, 5, 9};33int[] arr2 = {2, 3, 4, 6, 7};3435System.out.println("\nLeft:  " + Arrays.toString(arr1));36System.out.println("Right: " + Arrays.toString(arr2));3738int[] merged2 = mergeTwoSorted(arr1, arr2);39System.out.println("Merged: " + Arrays.toString(merged2));
    outputMerged: [1, 2, 3, 4, 5, 6, 7, 8]

Left:  [1, 5, 9]
Right: [2, 3, 4, 6, 7]

  9. k ← 0

    pass 2 of 2
    3public class MergeOnly {4    public static int[] mergeTwoSorted(int[] left, int[] right) {5        int[] result = new int[left.length3 + right.length5];6        int i = 0, j = 0, k→ 0 = 0;7        while (i < left.length && j < right.length) {

  10. k ← 8, i ← 3

    13}14while (i2 < left.length3) {15    result[k→ 8++] = left[i→ 3++];16}

  11. return result;

    21    return result;22}

  12. int[] merged2 = mergeTwoSorted(arr1, arr2);

    38    int[] merged2 = mergeTwoSorted(arr1, arr2);39    System.out.println("Merged: " + Arrays.toString(merged2));40}
    outputMerged: [1, 2, 3, 4, 5, 6, 7, 9]
Merge Operation The step that combines two sorted arrays into one sorted array by comparing the front values of each input.

Iterative Version

Bottom-up merge sort starts with runs of size one and repeatedly merges larger adjacent runs.

Iterative.java
Replay: real traced execution (multi-file project)
import java.util.Arrays;

public class Iterative {
    public static void mergeSortIterative(int[] arr) {
        int n = arr.length;
        for (int size = 1; size < n; size = size * 2) {
            for (int left = 0; left < n - 1; left += size * 2) {
                int mid = Math.min(left + size - 1, n - 1);
                int right = Math.min(left + size * 2 - 1, n - 1);

                merge(arr, left, mid, right);
            }
        }
    }
    public static void merge(int[] arr, int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;
        int[] leftArr = new int[n1];
        int[] rightArr = new int[n2];

        for (int i = 0; i < n1; i++)
            leftArr[i] = arr[left + i];
        for (int j = 0; j < n2; j++)
            rightArr[j] = arr[mid + 1 + j];

        int i = 0, j = 0, k = left;
        while (i < n1 && j < n2) {
            if (leftArr[i] <= rightArr[j]) {
                arr[k++] = leftArr[i++];
            } else {
                arr[k++] = rightArr[j++];
            }
        }

        while (i < n1) arr[k++] = leftArr[i++];
        while (j < n2) arr[k++] = rightArr[j++];
    }
    public static void main(String[] args) {
        int[] numbers = {38, 27, 43, 3, 9, 82, 10};

        System.out.println("Before: " + Arrays.toString(numbers));
        mergeSortIterative(numbers);
        System.out.println("After:  " + Arrays.toString(numbers));
    }
}

  1. public static void main(String[] args)

    37}38public static void main(String[] args) {39    int[] numbers = {38, 27, 43, 3, 9, 82, 10};4041    System.out.println("Before: " + Arrays.toString(numbers));42    mergeSortIterative(numbers);43    System.out.println("After:  " + Arrays.toString(numbers));
    outputBefore: [38, 27, 43, 3, 9, 82, 10]

  2. n ← 7

    3public class Iterative {4    public static void mergeSortIterative(int[] arr) {5        int n→ 7 = arr.length7;6        for (int size = 1; size < n; size = size * 2) {

  3. for (int size = 1; size < n; size = size * 2)

    pass 1 of 3
    5int n = arr.length;6for (int size1 = 1; size < n7; size = size * 2) {7    for (int left = 0; left < n - 1; left += size * 2) {
    All 3 passes — pass 1 is the card above
    passsize
    11
    22
    34

  4. mid ← 0, right ← 1

    pass 1 of 6
    6for (int size = 1; size < n; size = size * 2) {7    for (int left0 = 0; left < n7 - 1; left += size1 * 2) {8        int mid→ 0 = Math.min(left0 + size1 - 1, n7 - 1);9        int right→ 1 = Math.min(left0 + size1 * 2 - 1, n7 - 1);1011        merge(arr, left0, mid0, right1);12    }
    All 6 passes — pass 1 is the card above
    passleftsizemidright
    10101
    22123
    34145
    40213
    54256
    60436

  5. n1 ← 1, n2 ← 1

    pass 1 of 6
    14}15public static void merge(int[] arr, int left0, int mid0, int right1) {16    int n1→ 1 = mid0 - left0 + 1;17    int n2→ 1 = right1 - mid0;18    int[] leftArr = new int[n1];19    int[] rightArr = new int[n2];
    All 6 passes — pass 1 is the card above
    passleftmidrightn1n2
    100111
    222311
    344511
    401322
    545621
    603643

  6. leftArr[i] ← 38

    pass 1 of 11
    21for (int i0 = 0; i < n11; i++)22    leftArr[i]→ 38 = arr[left + i]38;23for (int j = 0; j < n2; j++)
    All 11 passes — pass 1 is the card above
    passin1arr[left + i]leftleftArr[i]
    1013800 → 38
    2014320 → 43
    301940 → 9
    4022700 → 27
    5123800 → 38
    602940 → 9
    7128240 → 82
    804300 → 3
    9142700 → 27
    10243800 → 38
    11344300 → 43

  7. rightArr[j] ← 27

    pass 1 of 9
    22    leftArr[i] = arr[left + i];23for (int j0 = 0; j < n21; j++)24    rightArr[j]→ 27 = arr[mid + 1 + j]27;
    All 9 passes — pass 1 is the card above
    passjn2arr[mid + 1 + j]midrightArr[j]
    1012700 → 27
    201320 → 3
    3018240 → 82
    402310 → 3
    5124310 → 43
    6011050 → 10
    703930 → 9
    8131030 → 10
    9238230 → 82

  8. k ← 0

    26int i = 0, j = 0, k→ 0 = left;27while (i < n1 && j < n2) {

  9. while (i < n1 && j < n2)

    pass 1 of 14
    26int i = 0, j = 0, k = left;27while (i0 < n11 && j0 < n21) {28    if (leftArr[i] <= rightArr[j]) {
    14 passes — pass 1 is the card above
    passin1jn2
    10101
    20101
    30101
    40202
    50212
    61212
    70201
    81201
    90403
    ⋯ 3 more passes ⋯
    132423
    143423

  10. k ← 1, j ← 1

    pass 1 of 6
    29    arr[k++] = leftArr[i++];30} else {31    arr[k→ 1++] = rightArr[j→ 1++];32}
    All 6 passes — pass 1 is the card above
    passkj
    10 → 10 → 1
    22 → 30 → 1
    30 → 10 → 1
    45 → 60 → 1
    51 → 20 → 1
    62 → 31 → 2

  11. k ← 2, i ← 1

    pass 1 of 3
    11            merge(arr, left0, mid0, right1);12        }13    }14}15public static void merge(int[] arr, int left, int mid, int right) {16    int n1 = mid - left + 1;17    int n2 = right - mid;18    int[] leftArr = new int[n1];19    int[] rightArr = new int[n2];2021    for (int i = 0; i < n1; i++)22        leftArr[i] = arr[left + i];23    for (int j = 0; j < n2; j++)24        rightArr[j] = arr[mid + 1 + j];2526    int i = 0, j = 0, k = left;27    while (i < n1 && j < n2) {28        if (leftArr[i] <= rightArr[j]) {29            arr[k++] = leftArr[i++];30        } else {31            arr[k++] = rightArr[j++];32        }33    }3435    while (i0 < n11) arr[k→ 2++] = leftArr[i++];36    while (j < n2) arr[k++] = rightArr[j++];
    All 3 passes — pass 1 is the card above
    passn1leftmidrightki
    110011 → 20 → 1
    212233 → 40 → 1
    324566 → 71 → 2

  12. k ← 2

    26int i = 0, j = 0, k→ 2 = left;27while (i < n1 && j < n2) {

  13. k ← 4

    26int i = 0, j = 0, k→ 4 = left;27while (i < n1 && j < n2) {

  14. k ← 5, i ← 1

    pass 1 of 8
    27while (i < n1 && j < n2) {28    if (leftArr[i]9 <= rightArr[j]82) {29        arr[k→ 5++] = leftArr[i→ 1++];30    } else {
    All 8 passes — pass 1 is the card above
    passleftArr[i]rightArr[j]jki
    198204 → 50 → 1
    2274311 → 20 → 1
    3384312 → 31 → 2
    491004 → 50 → 1
    53900 → 10 → 1
    6278223 → 41 → 2
    7388224 → 52 → 3
    8438225 → 63 → 4

  15. k ← 6, j ← 1

    pass 1 of 3
    11            merge(arr, left4, mid4, right5);12        }13    }14}15public static void merge(int[] arr, int left, int mid, int right) {16    int n1 = mid - left + 1;17    int n2 = right - mid;18    int[] leftArr = new int[n1];19    int[] rightArr = new int[n2];2021    for (int i = 0; i < n1; i++)22        leftArr[i] = arr[left + i];23    for (int j = 0; j < n2; j++)24        rightArr[j] = arr[mid + 1 + j];2526    int i = 0, j = 0, k = left;27    while (i < n1 && j < n2) {28        if (leftArr[i] <= rightArr[j]) {29            arr[k++] = leftArr[i++];30        } else {31            arr[k++] = rightArr[j++];32        }33    }3435    while (i < n1) arr[k++] = leftArr[i++];36    while (j0 < n21) arr[k→ 6++] = rightArr[j++];37}
    All 3 passes — pass 1 is the card above
    passn2leftmidrightkj
    114455 → 60 → 1
    220133 → 41 → 2
    330366 → 72 → 3

  16. k ← 0

    26int i = 0, j = 0, k→ 0 = left;27while (i < n1 && j < n2) {

  17. k ← 4

    26int i = 0, j = 0, k→ 4 = left;27while (i < n1 && j < n2) {

  18. k ← 0

    26int i = 0, j = 0, k→ 0 = left;27while (i < n1 && j < n2) {

  19. mergeSortIterative(numbers);

    41    System.out.println("Before: " + Arrays.toString(numbers));42    mergeSortIterative(numbers);43    System.out.println("After:  " + Arrays.toString(numbers));44}
    outputAfter:  [3, 9, 10, 27, 38, 43, 82]

Practical Use

Merge sort is useful when stable, predictable sorting matters.

Practical.java
Replay: real traced execution (multi-file project)
import java.util.Arrays;

class Student {
    String name;
    int score;

    Student(String name, int score) {
        this.name = name;
        this.score = score;
    }

    public String toString() {
        return name + ":" + score;
    }
}

public class Practical {
    public static void mergeSort(Student[] arr, int left, int right) {
        if (left < right) {
            int mid = left + (right - left) / 2;
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);
            merge(arr, left, mid, right);
        }
    }
    public static void merge(Student[] arr, int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;
        Student[] leftArr = new Student[n1];
        Student[] rightArr = new Student[n2];

        for (int i = 0; i < n1; i++)
            leftArr[i] = arr[left + i];
        for (int j = 0; j < n2; j++)
            rightArr[j] = arr[mid + 1 + j];

        int i = 0, j = 0, k = left;
        while (i < n1 && j < n2) {
            if (leftArr[i].score >= rightArr[j].score) {
                arr[k++] = leftArr[i++];
            } else {
                arr[k++] = rightArr[j++];
            }
        }

        while (i < n1) arr[k++] = leftArr[i++];
        while (j < n2) arr[k++] = rightArr[j++];
    }
    public static void main(String[] args) {
        Student[] students = {
            new Student("Alice", 85),
            new Student("Bob", 92),
            new Student("Charlie", 78),
            new Student("Diana", 95),
            new Student("Eve", 88)
        };

        System.out.println("Before: " + Arrays.toString(students));
        mergeSort(students, 0, students.length - 1);
        System.out.println("After:  " + Arrays.toString(students));

        System.out.println("\nTop 3 students:");
        for (int i = 0; i < 3 && i < students.length; i++) {
            System.out.println((i + 1) + ". " + students[i]);
        }
    }
}

  1. public static void main(String[] args)

    48}49public static void main(String[] args) {50    Student[] students = {51        new Student("Alice", 85),52        new Student("Bob", 92),53        new Student("Charlie", 78),54        new Student("Diana", 95),55        new Student("Eve", 88)56    };

  2. this.name ← Alice, this.score ← 85

    pass 1 of 5
    7Student(String nameAlice, int score85) {8    this.name→ Alice = nameAlice;9    this.score→ 85 = score85;10}
    All 5 passes — pass 1 is the card above
    passnamescorethis.namethis.score
    1Alice85Alice85
    2Bob92Bob92
    3Charlie78Charlie78
    4Diana95Diana95
    5Eve88Eve88

  3. Student[] students =

    49public static void main(String[] args) {50    Student[] students = {51        new Student("Alice", 85),52        new Student("Bob", 92),53        new Student("Charlie", 78),54        new Student("Diana", 95),55        new Student("Eve", 88)56    };5758    System.out.println("Before: " + Arrays.toString(students));59    mergeSort(students, 0, students.length5 - 1);60    System.out.println("After:  " + Arrays.toString(students));
    outputBefore: [Alice:85, Bob:92, Charlie:78, Diana:95, Eve:88]

  4. public static void mergeSort(Student[] arr, int left, int right)

    pass 1 of 9
    17public class Practical {18    public static void mergeSort(Student[] arr, int left0, int right4) {19        if (left < right) {
    All 9 passes — pass 1 is the card above
    passleftrightmid
    104—
    202—
    301—
    4000
    5110
    6221
    734—
    8333
    9443

  5. mid ← 2

    pass 1 of 4
    18public static void mergeSort(Student[] arr, int left, int right) {19    if (left0 < right4) {20        int mid→ 2 = left0 + (right4 - left) / 2;21        mergeSort(arr, left0, mid2);22        mergeSort(arr, mid + 1, right);
    All 4 passes — pass 1 is the card above
    passleftrightmid
    1042
    2021
    3010
    4343

  6. n1 ← 1, n2 ← 1

    pass 1 of 4
    25}26public static void merge(Student[] arr, int left0, int mid0, int right1) {27    int n1→ 1 = mid0 - left0 + 1;28    int n2→ 1 = right1 - mid0;29    Student[] leftArr = new Student[n1];30    Student[] rightArr = new Student[n2];
    All 4 passes — pass 1 is the card above
    passleftmidrightn1n2
    100111
    201221
    333411
    402432

  7. leftArr[i] ← Alice:85

    pass 1 of 7
    32for (int i0 = 0; i < n11; i++)33    leftArr[i]→ Alice:85 = arr[left + i]Alice:85;34for (int j = 0; j < n2; j++)
    All 7 passes — pass 1 is the card above
    passin1arr[left + i]leftleftArr[i]
    101Alice:850null → Alice:85
    202Bob:920null → Bob:92
    312Alice:850null → Alice:85
    401Diana:953null → Diana:95
    503Bob:920null → Bob:92
    613Alice:850null → Alice:85
    723Charlie:780null → Charlie:78

  8. rightArr[j] ← Bob:92

    pass 1 of 5
    33    leftArr[i] = arr[left + i];34for (int j0 = 0; j < n21; j++)35    rightArr[j]→ Bob:92 = arr[mid + 1 + j]Bob:92;
    All 5 passes — pass 1 is the card above
    passjn2arr[mid + 1 + j]midrightArr[j]
    101Bob:920null → Bob:92
    201Charlie:781null → Charlie:78
    301Eve:883null → Eve:88
    402Diana:952null → Diana:95
    512Eve:882null → Eve:88

  9. k ← 0

    37int i = 0, j = 0, k→ 0 = left;38while (i < n1 && j < n2) {

  10. while (i < n1 && j < n2)

    pass 1 of 7
    37int i = 0, j = 0, k = left;38while (i0 < n11 && j0 < n21) {39    if (leftArr[i].score >= rightArr[j].score) {
    All 7 passes — pass 1 is the card above
    passin1n2kjleftmidright
    1011—0———
    2021—0———
    31212 → 30 → 101 → 22
    40114 → 50 → 1024
    5032—0———
    6032—1———
    7132—1———

  11. k ← 1, j ← 1

    pass 1 of 3
    40    arr[k++] = leftArr[i++];41} else {42    arr[k→ 1++] = rightArr[j→ 1++];43}
    All 3 passes — pass 1 is the card above
    passkj
    10 → 10 → 1
    20 → 10 → 1
    32 → 31 → 2

  12. k ← 2, i ← 1, left ← 0, mid ← 1

    pass 1 of 3
    20        int mid = left + (right - left) / 2;21        mergeSort(arr, left→ 0, mid→ 1);22        mergeSort(arr, mid1 + 1, right2);23        merge(arr, left0, mid0, right1);24    }25}26public static void merge(Student[] arr, int left, int mid, int right) {27    int n1 = mid - left + 1;28    int n2 = right - mid;29    Student[] leftArr = new Student[n1];30    Student[] rightArr = new Student[n2];3132    for (int i = 0; i < n1; i++)33        leftArr[i] = arr[left + i];34    for (int j = 0; j < n2; j++)35        rightArr[j] = arr[mid + 1 + j];3637    int i = 0, j = 0, k = left;38    while (i < n1 && j < n2) {39        if (leftArr[i].score >= rightArr[j].score) {40            arr[k++] = leftArr[i++];41        } else {42            arr[k++] = rightArr[j++];43        }44    }4546    while (i0 < n11) arr[k→ 2++] = leftArr[i++];47    while (j < n2) arr[k++] = rightArr[j++];
    All 3 passes — pass 1 is the card above
    passn1rightkileftmid
    1111 → 20 → 100 → 1
    23—3 → 41 → 2——
    3344 → 52 → 302

  13. k ← 0

    37int i = 0, j = 0, k→ 0 = left;38while (i < n1 && j < n2) {

  14. k ← 1, i ← 1

    pass 1 of 4
    38while (i < n1 && j < n2) {39    if (leftArr[i].score92 >= rightArr[j].score78) {40        arr[k→ 1++] = leftArr[i→ 1++];41    } else {
    All 4 passes — pass 1 is the card above
    passleftArr[i].scoreleftArr[i]rightArr[j].scorerightArr[j]n2kijleftmidright
    192Bob:9278Charlie:78—0 → 10 → 10———
    285Alice:8578Charlie:7811 → 21 → 20 → 101 → 22
    395Diana:9588Eve:8813 → 40 → 10 → 1024
    492Bob:9288Eve:88—1 → 20 → 11———

  15. k ← 3, j ← 1, left ← 0, mid ← 2

    pass 1 of 2
    20        int mid = left + (right - left) / 2;21        mergeSort(arr, left→ 0, mid→ 2);22        mergeSort(arr, mid2 + 1, right4);23        merge(arr, left0, mid1, right2);24    }25}26public static void merge(Student[] arr, int left, int mid, int right) {27    int n1 = mid - left + 1;28    int n2 = right - mid;29    Student[] leftArr = new Student[n1];30    Student[] rightArr = new Student[n2];3132    for (int i = 0; i < n1; i++)33        leftArr[i] = arr[left + i];34    for (int j = 0; j < n2; j++)35        rightArr[j] = arr[mid + 1 + j];3637    int i = 0, j = 0, k = left;38    while (i < n1 && j < n2) {39        if (leftArr[i].score >= rightArr[j].score) {40            arr[k++] = leftArr[i++];41        } else {42            arr[k++] = rightArr[j++];43        }44    }4546    while (i < n1) arr[k++] = leftArr[i++];47    while (j0 < n21) arr[k→ 3++] = rightArr[j++];48}

  16. k ← 3

    37int i = 0, j = 0, k→ 3 = left;38while (i < n1 && j < n2) {

  17. k ← 5, j ← 1, mid ← 2, right ← 4

    pass 2 of 2
    21        mergeSort(arr, left, mid);22        mergeSort(arr, mid→ 2 + 1, right→ 4);23        merge(arr, left0, mid2, right4);24    }25}26public static void merge(Student[] arr, int left, int mid, int right) {27    int n1 = mid - left + 1;28    int n2 = right - mid;29    Student[] leftArr = new Student[n1];30    Student[] rightArr = new Student[n2];3132    for (int i = 0; i < n1; i++)33        leftArr[i] = arr[left + i];34    for (int j = 0; j < n2; j++)35        rightArr[j] = arr[mid + 1 + j];3637    int i = 0, j = 0, k = left;38    while (i < n1 && j < n2) {39        if (leftArr[i].score >= rightArr[j].score) {40            arr[k++] = leftArr[i++];41        } else {42            arr[k++] = rightArr[j++];43        }44    }4546    while (i < n1) arr[k++] = leftArr[i++];47    while (j0 < n21) arr[k→ 5++] = rightArr[j++];48}

  18. k ← 0

    37int i = 0, j = 0, k→ 0 = left;38while (i < n1 && j < n2) {

  19. mergeSort(students, 0, students.length - 1);

    58System.out.println("Before: " + Arrays.toString(students));59mergeSort(students, 0, students.length5 - 1);60System.out.println("After:  " + Arrays.toString(students));6162System.out.println("\nTop 3 students:");63for (int i = 0; i < 3 && i < students.length; i++) {
    outputAfter:  [Diana:95, Bob:92, Eve:88, Alice:85, Charlie:78]

Top 3 students:

  20. for (int i = 0; i < 3 && i < students.length; i++)

    pass 1 of 3
    62System.out.println("\nTop 3 students:");63for (int i0 = 0; i < 3 && i < students.length5; i++) {64    System.out.println((i0 + 1) + ". " + students[i]Diana:95);65}
    output1. Diana:95
    All 3 passes — pass 1 is the card above
    passistudents[i]
    10Diana:95
    21Bob:92
    32Eve:88

Exercise: Practical.java

Implement a merge function that counts the number of inversions while merging