MergeSort

1.MergeSort.pseudo

MergeSort(arr, low, high):
  arr = array of unsorted integers
  low = integer, initially 0
  high = integer, initially size(arr) - 1

  if low >= high then return

  mid = floor((low + high) / 2)

  MergeSort(arr, low, mid)
  MergeSort(arr, mid + 1, high)

  Merge(arr, low, mid, high)


Merge(arr, low, mid, high):
  arr = array of unsorted integers
  low = integer, initially 0
  mid = midpoint of arr, initially floor((size(arr) - 1) / 2)
  high = integer, initially size(arr) - 1

  leftSize = mid - low + 1
  rightSize = high - mid

  left = new empty array of size leftSize
  copy all elements from arr in range low...leftSize into left

  right = new empty array of size rightSize
  copy all elements from arr in range (mid + 1)...rightSize into right

  leftIdx = 0, rightIdx = 0, curPos = low

  while leftIdx < leftSize and rightIdx < rightSize:
    if left[leftIdx] >= right[rightIdx] then
      arr[curPos] = right[rightIdx]
      rightIdx++
    else then
      arr[curPos] = left[leftIdx]
      leftIdx++
  
    arrPos++

  while leftIdx < leftSize:
    arr[curPos] = left[leftIdx]
    leftIdx++, curPos++

  while rightIdx < rightSize:
    arr[curPos] = right[rightIdx]
    rightIdx++, curPos++

2.MergeSort.java

import java.util.Arrays;

public class MergeSort {
    // driver
    public static void main(String[] args) {
        final int[] array = new int[] { 3, 1, -10, 4, 59, 2 };

        System.out.printf("Input array: %s%n", Arrays.toString(array));

        mergeSort(array);

        System.out.printf("Sorted array: %s%n", Arrays.toString(array));
    }

    public static void mergeSort(int[] arr) {
        mergeSort(arr, 0, arr.length - 1);
    }
  
    public static void mergeSort(final int[] arr, final int low, final int high) {
        if (low >= high) {
            return;
        }

        final int mid = (low + high) / 2;

        mergeSort(arr, low, mid);
        mergeSort(arr, mid + 1, high);
        merge(arr, low, mid, high);
    }

    private static void merge(final int[] arr, final int low, final int mid, final int high) {
        final int leftSize = mid - low + 1;
        final int[] left = new int[leftSize];
        System.arraycopy(arr, low, left, 0, leftSize);

        final int rightSize = high - mid;
        final int[] right = new int[rightSize];
        System.arraycopy(arr, mid + 1, right, 0, rightSize);

        int leftIdx = 0, rightIdx = 0, arrPos = low;
        while (leftIdx < leftSize && rightIdx < rightSize) {
            final int leftNum = left[leftIdx];
            final int rightNum = right[rightIdx];

            if (leftNum >= rightNum) {
                arr[arrPos] = right[rightIdx];
                rightIdx++;
            } else {
                arr[arrPos] = left[leftIdx];
                leftIdx++;
            }

            arrPos++;
        }

        while (leftIdx < leftSize) {
            arr[arrPos] = left[leftIdx];
            leftIdx++;
            arrPos++;
        }

        while (rightIdx < rightSize) {
            arr[arrPos] = right[rightIdx];
            rightIdx++;
            arrPos++;
        }
    }
}

3.output-on-test.txt

Input array: [3, 1, -10, 4, 59, 2]
...calling merge sort...
mergeSort([3, 1, -10, 4, 59, 2], 0, 5) called
...mid = 2...
mergeSort([3, 1, -10, 4, 59, 2], 0, 2) called
...mid = 1...
mergeSort([3, 1, -10, 4, 59, 2], 0, 1) called
...mid = 0...
merge([3, 1, -10, 4, 59, 2], 0, 0, 1) called
...comparing left (3) and right (1)...
...leftNum >= rightNum ---> ordering right ahead of left...
...placing remaining left-side digits...
...placing 3...
...arr is now [1, 3, -10, 4, 59, 2]...
merge([1, 3, -10, 4, 59, 2], 0, 1, 2) called
...comparing left (1) and right (-10)...
...leftNum >= rightNum ---> ordering right ahead of left...
...placing remaining left-side digits...
...placing 1...
...placing 3...
...arr is now [-10, 1, 3, 4, 59, 2]...
mergeSort([-10, 1, 3, 4, 59, 2], 3, 5) called
...mid = 4...
mergeSort([-10, 1, 3, 4, 59, 2], 3, 4) called
...mid = 3...
merge([-10, 1, 3, 4, 59, 2], 3, 3, 4) called
...comparing left (4) and right (59)...
...rightNum > leftNum ---> ordering left ahead of right...
...placing remaining right-side digits...
...placing 59...
...arr is now [-10, 1, 3, 4, 59, 2]...
merge([-10, 1, 3, 4, 59, 2], 3, 4, 5) called
...comparing left (4) and right (2)...
...leftNum >= rightNum ---> ordering right ahead of left...
...placing remaining left-side digits...
...placing 4...
...placing 59...
...arr is now [-10, 1, 3, 2, 4, 59]...
merge([-10, 1, 3, 2, 4, 59], 0, 2, 5) called
...comparing left (-10) and right (2)...
...rightNum > leftNum ---> ordering left ahead of right...
...comparing left (1) and right (2)...
...rightNum > leftNum ---> ordering left ahead of right...
...comparing left (3) and right (2)...
...leftNum >= rightNum ---> ordering right ahead of left...
...comparing left (3) and right (4)...
...rightNum > leftNum ---> ordering left ahead of right...
...placing remaining right-side digits...
...placing 4...
...placing 59...
...arr is now [-10, 1, 2, 3, 4, 59]...
Sorted array: [-10, 1, 2, 3, 4, 59]