DEV Community

Maulana Ifandika
Maulana Ifandika

Posted on

1

Merge Sort Algorithm

Algorithm Learning Journey

MergeSort Algo

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.
MergeSort

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

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

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

For the complete process.
MergeSort

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++];
    }
}
Enter fullscreen mode Exit fullscreen mode

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];
}
Enter fullscreen mode Exit fullscreen mode

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);
Enter fullscreen mode Exit fullscreen mode

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++];
}
Enter fullscreen mode Exit fullscreen mode

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++];
    }
}
Enter fullscreen mode Exit fullscreen mode

And this statement is interesting.

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

Let’s simplify it

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

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++];
        }
    }
}
Enter fullscreen mode Exit fullscreen mode

Enjoy your journey :)

Reinvent your career. Join DEV.

It takes one minute and is worth it for your career.

Get started

Top comments (0)

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more

👋 Kindness is contagious

Explore a sea of insights with this enlightening post, highly esteemed within the nurturing DEV Community. Coders of all stripes are invited to participate and contribute to our shared knowledge.

Expressing gratitude with a simple "thank you" can make a big impact. Leave your thanks in the comments!

On DEV, exchanging ideas smooths our way and strengthens our community bonds. Found this useful? A quick note of thanks to the author can mean a lot.

Okay