Languages
[Edit]
EN

Java - merge sort implementation algorithm (custom)

6 points
Created by:
AnnLen
9180

Merge sort is a D&C (Divide and Conquer) algorithm. Like quick sort average time complexity is O(n log n). But the difference is that merge sort worst time complexity is also O(n log n) as quick sort O(n^2). Qucik sort adventage over merge sort is that it requires less memory, thus quick sort has better space complexity.

Java - merge sort implementation

import java.util.Arrays;

public class SortUtil {

    public static void mergeSort(int[] arr) {
        int[] buff = new int[arr.length];
        mergeSort(arr, buff, 0, arr.length - 1);
    }

    private static void mergeSort(int[] arr, int[] buff, int lo, int hi) {
        if (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            mergeSort(arr, buff, lo, mid);
            mergeSort(arr, buff, mid + 1, hi);

            for (int i = lo; i <= hi; i++) {
                buff[i] = arr[i];
            }
            int i = lo;
            int j = mid + 1;
            int k = lo;

            while (i <= mid && j <= hi) {
                if (buff[i] <= buff[j]) {
                    arr[k++] = buff[i++];
                } else {
                    arr[k++] = buff[j++];
                }
            }
            while (i <= mid) {
                arr[k++] = buff[i++];
            }
        }
    }

    public static void main(String[] args) {
        int[] array = {2, 8, 1, 4, 5, 6, 3};

        // [2, 8, 1, 4, 5, 6, 3]
        System.out.println(Arrays.toString(array));

        mergeSort(array);

        // [1, 2, 3, 4, 5, 6, 8]
        System.out.println(Arrays.toString(array));
    }
}

Output:

[2, 8, 1, 4, 5, 6, 3]
[1, 2, 3, 4, 5, 6, 8]

Complex unit test with order assertion

import com.google.common.base.Stopwatch;
import org.junit.Test;

import java.util.Arrays;
import java.util.concurrent.ThreadLocalRandom;

public class SortUtilTests {
    
    @Test
    public void test1 () {
        int[] array = {2, 8, 1, 4, 5, 6, 3};
        System.out.println(Arrays.toString(array));

        SortUtil.mergeSort(array);
        assertSortedArray(array);
        System.out.println(Arrays.toString(array));
    }

    @Test
    public void test2 () {
        int[] array = new int[6]; // even number array size
        for (int i = 0; i < array.length; i++) {
            array[i] = nextInt(100, 2_000_000);
        }
        System.out.println(Arrays.toString(array));

        SortUtil.mergeSort(array);
        assertSortedArray(array);
        System.out.println(Arrays.toString(array));
    }

    @Test
    public void test3 () {
        int[] array = new int[7]; // odd number array size
        for (int i = 0; i < array.length; i++) {
            array[i] = nextInt(100, 2_000_000);
        }

        array[4] = 0;
        array[1] = Integer.MAX_VALUE;

        // [1419647, 155906, 1113132, 702682, 1700450, 1279031, 1326543]
        System.out.println(Arrays.toString(array));

        SortUtil.mergeSort(array);
        assertSortedArray(array);

        // [155906, 702682, 1113132, 1279031, 1326543, 1419647, 1700450]
        System.out.println(Arrays.toString(array));
    }

    @Test
    public void test4 () {
        int[] array = new int[214_578];
        for (int i = 0; i < array.length; i++) {
            array[i] = nextInt(100, 2_000_000);
        }

        System.out.println("Array size: " + array.length);

        System.out.println("BEFORE sorting - first and last element");
        System.out.println(array[0]);
        System.out.println(array[array.length - 1]);

        Stopwatch stopwatch = Stopwatch.createStarted();
        SortUtil.mergeSort(array);

        // 48.42 ms
        System.out.println(stopwatch.stop());

        assertSortedArray(array);

        System.out.println("AFTER sorting - first and last element");
        System.out.println(array[0]);
        System.out.println(array[array.length - 1]);
    }

    @Test
    public void test5 () {
        int[] array = new int[5_000_000];
        for (int i = 0; i < array.length; i++) {
            array[i] = nextInt(100, 2_000_000_000);
        }

        System.out.println(array[0]);
        System.out.println(array[array.length - 1]);

        Stopwatch stopwatch = Stopwatch.createStarted();
        SortUtil.mergeSort(array);

        // 832.2 ms
        System.out.println(stopwatch.stop());

        assertSortedArray(array);

        System.out.println(array[0]);
        System.out.println(array[array.length - 1]);
    }

    private static int nextInt(int min, int max) {
        return ThreadLocalRandom.current().nextInt(min, max);
    }

    private void assertSortedArray(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            if (array[i] > array[i + 1]) {
                throw new RuntimeException(
                        array[i] + " is larger then " + array[i + 1]
                                + ", index: " + i + ", index2: " + (i + 1));
            }
        }
    }
}

Compare speed

Now we will compare speed of:

  • buble sort
  • this article merge sort impelmentation
  • quick sort - JDK implementation - Arrays.sort()

Bubble sort only on 50_000 elements array as it takes more then 4 secounds.

Merge sort and quick sort on array of 5_000_000 elements and we use the same seed with Random class to generate the same random numbers to have good comparing test.

import com.google.common.base.Stopwatch;
import org.junit.Test;

import java.util.Arrays;
import java.util.Random;

public class SortUtilCompareTest {

    public static int nextInt(int min, int max, Random random) {
        return random.nextInt((max - min) + 1) + min;
    }

    // array of size 50_000 elements
    @Test
    public void test_simple_bubble_sort () {
        Random random = new Random(3819201);

        int[] array = new int[50_000];

        for (int i = 0; i < array.length; i++) {
            int randomInt = nextInt(100, 2_000_000_000, random);
            array[i] = randomInt;
        }

        Stopwatch stopwatch = Stopwatch.createStarted();

        // simple bubble sort - O(n ^ 2) time complexity
        for (int i = 0; i < array.length; i++) {
            for (int j = i + 1; j < array.length; j++) {
                if (array[i] > array[j]) {
                    int tmp = array[i];
                    array[i] = array[j];
                    array[j] = tmp;
                }
            }
        }

        System.out.println(stopwatch.stop()); // 4.236 s

        assertSortedArray(array);
    }

    // array of size 5_000_000 elements
    @Test
    public void test_our_custom_merge_sort_impl () {
        Random random = new Random(3819201);

        int[] array = new int[5_000_000];

        for (int i = 0; i < array.length; i++) {
            int randomInt = nextInt(100, 2_000_000_000, random);
            array[i] = randomInt;
        }

        Stopwatch stopwatch = Stopwatch.createStarted();
        SortUtil.mergeSort(array);
        System.out.println(stopwatch.stop()); // 889.3 ms

        assertSortedArray(array);
    }

    // array of size 5_000_000 elements
    @Test
    public void test_jdk_quick_sort () {
        Random random = new Random(3819201);

        int[] array = new int[5_000_000];

        for (int i = 0; i < array.length; i++) {
            int randomInt = nextInt(100, 2_000_000_000, random);
            array[i] = randomInt;
        }

        Stopwatch stopwatch = Stopwatch.createStarted();
        Arrays.sort(array);
        System.out.println(stopwatch.stop()); // 633.3 ms

        assertSortedArray(array);
    }

    private void assertSortedArray(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            if (array[i] > array[i + 1]) {
                throw new RuntimeException(
                        array[i] + " is larger then " + array[i + 1]
                                + ", index: " + i + ", index2: " + (i + 1));
            }
        }
    }
}

References

Native Advertising
50 000 ad impressions - 449$
🚀
Get your tech brand or product in front of software developers.
For more information contact us:
Red dot
Dirask - friendly IT community for everyone.

❤️💻 🙂

Join