Merge Sort Algorithm

Algorithm Learning Journey

The Merge Sort algorithm is an algorithm that has the principle/way of dividing and merging. What is meant by dividing is breaking an array into small fractions that cannot be divided, then the array is sorted at the same time as the process of merging the array. In the combining stage the sorting process occurs, not in the dividing/splitting process.

Illustration
There is an array.

Then we break array into 2 parts (left & right). By creating a new array then entering the array values.

Then break again until n(array length) <= 1.

Then the next stage, the values ​​are combined and sorted, smaller values ​​on the left side & larger values ​​on the right.

For the complete process.

Code Implementation
Java

public static void mergeSort(int[] array) {
    int n = array.length;
    if(n <= 1) return;

    int middle = (n / 2);
    int[] left = new int[middle];
    int[] right = new int[n - middle];

    for(int i = 0; i < middle; i++) {
        left[i] = array[i];
    }
    int supportIndex = 0;
    for(int i = middle; i < n; i++) {
        right[supportIndex++] = array[i];
    }

    mergeSort(left);
    mergeSort(right);
    merge(left, right, array);
}

private static void merge(int[] left, int[] right, int[] array) {
    int leftIndex = 0,
        rightIndex = 0,
        arrayIndex = 0,
        leftSize = left.length,
        rightSize = right.length;

    while(leftIndex < leftSize && rightIndex < rightSize) {
        if(left[leftIndex] < right[rightIndex]) {
            array[arrayIndex++] = left[leftIndex++];
        }
        else {
            array[arrayIndex++] = right[rightIndex++];
        }
    }

    while(leftIndex < leftSize) {
        array[arrayIndex++] = left[leftIndex++];
    }
    while(rightIndex < rightSize) {
        array[arrayIndex++] = right[rightIndex++];
    }
}

This code runs and works, but it’s not effective enough, let’s fix it. First when looking at this code, like 1 thing we want to do is move the array values ​​to the left and right arrays.

for(int i = 0; i < middle; i++) {
    left[i] = array[i];
}
int supportIndex = 0;
for(int i = middle; i < n; i++) 
    right[supportIndex++] = array[i];
}

So let’s fix with a function on Arrays.

import java.util.Arrays;
...
// Nice
left = Arrays.copyOfRange(array, 0, middle);
right = Arrays.copyOfRange(array, middle, n);

Then the second is this code.

while(leftIndex < leftSize && rightIndex < rightSize) {
    if(left[leftIndex] < right[rightIndex]) {
        array[arrayIndex++] = left[leftIndex++];
    }
    else {
        array[arrayIndex++] = right[rightIndex++];
    }
}

while(leftIndex < leftSize) {
    array[arrayIndex++] = left[leftIndex++];
}
while(rightIndex < rightSize) {
    array[arrayIndex++] = right[rightIndex++];
}

This code aims to sort the array and apply it to the original array, so let’s make it one “while”.

while (leftIndex < leftSize || rightIndex < rightSize) {
    if(leftIndex < leftSize && rightIndex < rightSize) {
        if(left[leftIndex] < right[rightIndex]) {
            array[arrayIndex++] = left[leftIndex++];
        }
        else {
            array[arrayIndex++] = right[rightIndex++];
        }
    }
    else if(leftIndex < leftSize) {
        array[arrayIndex++] = left[leftIndex++];
    }
    else if(rightIndex < rightSize) {
        array[arrayIndex++] = right[rightIndex++];
    }
}

And this statement is interesting.

else if(leftIndex < leftSize) {
    array[arrayIndex++] = left[leftIndex++];
}
else if(rightIndex < rightSize) {
    array[arrayIndex++] = right[rightIndex++];
}

Let’s simplify it

while(leftIndex < leftSize) {
    array[arrayIndex++] = left[leftIndex++];
}
while(rightIndex < rightSize) {
    array[arrayIndex++] = right[rightIndex++];
}

Lastly, for the complete code.

public static void mergeSort(int[] array) {
    int n = array.length;
    if(n <= 1) return;

    int middle = (n / 2);
    int[] left = new int[middle];
    int[] right = new int[n - middle];

    left = Arrays.copyOfRange(array, 0, middle);
    right = Arrays.copyOfRange(array, middle, n);

    mergeSort(left);
    mergeSort(right);
    merge(left, right, array);
}

private static void merge(int[] left, int[] right, int[] array) {
    int leftIndex = 0,
        rightIndex = 0,
        arrayIndex = 0,
        leftSize = left.length,
        rightSize = right.length;

    while (leftIndex < leftSize || rightIndex < rightSize) {
        if(leftIndex < leftSize && rightIndex < rightSize) {
            if(left[leftIndex] < right[rightIndex]) {
                array[arrayIndex++] = left[leftIndex++];
            }
            else {
                array[arrayIndex++] = right[rightIndex++];
            }
        }
        while(leftIndex < leftSize) {
            array[arrayIndex++] = left[leftIndex++];
        }
        while(rightIndex < rightSize) {
            array[arrayIndex++] = right[rightIndex++];
        }
    }
}

Enjoy your journey :)