Merge Sort Algorithm

Maulana Ifandika — Tue, 21 Jan 2025 12:09:16 +0000

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 :)

Difference Java ByteArrayOutputStream.write(int n) with ByteArrayOutputStream.write(byte[] b, int off, int len)

Maulana Ifandika — Tue, 21 Jan 2025 08:56:58 +0000

This function is used to write/enter data from the stream that we are opening, in this case I will try to download image data via the internet with a url. Let's try it.

Code #write(byte[] b, int off, int len)

String val = "https://akcdn.detik.net.id/community/media/visual/2023/03/04/sholat-jenazah_169.jpeg";
URL url = new URL(val);
InputStream in = new BufferedInputStream(url.openStream());
ByteArrayOutputStream out = new ByteArrayOutputStream();
byte[] buf = new byte[1024];
int n = 0;

while (-1 != (n=in.read(buf))) {
  out.write(buf, 0, n);
}
out.close();
in.close();

byte[] response = out.toByteArray();
FileOutputStream fos = new FileOutputStream("D:/my-image1.jpg");
fos.write(response);
fos.close();

Code #write(int n)

String val = "https://akcdn.detik.net.id/community/media/visual/2023/03/04/sholat-jenazah_169.jpeg";
URL url = new URL(val);
InputStream in = new BufferedInputStream(url.openStream());
ByteArrayOutputStream out = new ByteArrayOutputStream();
int n = 0;

while (-1 != (n=in.read(buf))) {
  out.write(n);
}
out.close();
in.close();

byte[] response = out.toByteArray();
FileOutputStream fos = new FileOutputStream("D:/my-image1.jpg");
fos.write(response);
fos.close();

Result
For the result of image file.

There are differences when looking at the properties of the two files.

my-image1.jpg

my-image2.jpg

You can see in the size that there is a difference in the size value.

Forem: Maulana Ifandika

Merge Sort Algorithm

Difference Java ByteArrayOutputStream.write(int n) with ByteArrayOutputStream.write(byte[] b, int off, int len)