Mergesort is a fast sorting algorithm, see the implementation in Java.

Configuration

Java Compilation:
Java Runtime:

JDK 11.0.12
JRE HotSpot 11.0.12


import java.util.Random;

public class MainClass {

    final static int TOTAL = 50;

    public static void main(String[] args) {

        int[] elements = new int[TOTAL];

        Random random = new Random();

        for (int i = 0; i < TOTAL; i++) {
            elements[i] = random.nextInt(TOTAL);
        }

        System.out.println("started: ");
        for (int i = 0; i < TOTAL; i++) {
            System.out.print(elements[i] + " ");
        }

        mergeSort(elements, 0, TOTAL - 1);

        System.out.println();
        System.out.println("Done: ");

        for (int i = 0; i < TOTAL; i++) {
            System.out.print(elements[i] + " ");
        }
    }

    private static void mergeSort(int[] elements, int from, int to) {

        if (to - from <= 1) {
            if (to - from == 1) {
                if (elements[from] > elements[to]) {
                    int temp = elements[from];
                    elements[from] = elements[to];
                    elements[to] = temp;
                }
            }
            return;
        }

        int middle = (from + to) / 2;

        mergeSort(elements, from, middle);
        mergeSort(elements, middle + 1, to);

        int[] merged = new int[to - from + 1];
        int count = 0;

        int left = from;
        int right = middle + 1;

        do {
            if (left > middle) {
                merged[count++] = elements[right++];
            }
            else if (right > to) {
                merged[count++] = elements[left++];
            }
            else if (elements[left] > elements[right]) {
                merged[count++] = elements[right++];
            }
            else {
                merged[count++] = elements[left++];
            }
        } while (left <= middle || right <= to);

        count = 0;
        for (int i = from; i <= to; i++) {
            elements[i] = merged[count++];
        }
    }
}

Some note about the code:

The input is an unsorted int array, with the values assigned randomly
The idea of mergesort is divide and conquer. First it will divide the elements into 2 groups, then mergesort each of them
After mergesort each of the group, the 2 group each will be sorted. Then merge the 2 sorted group back into a sorted int array
If just 2 elements to sort, simply compare them and return. if even less than 2 elements to sort, simply return

Sample output:


started:

44 29 7 30 30 35 16 11 23 34 48 14 7 42 18 26 12 24 15 25 2 49 34 2 21 29 41 37 20 17 29 8 49 12 5 37 32 23 19 13 32 44 48 10 15 35 0 47 14 33

Done:

0 2 2 5 7 7 8 10 11 12 12 13 14 14 15 15 16 17 18 19 20 21 23 23 24 25 26 29 29 29 30 30 32 32 33 34 34 35 35 37 37 41 42 44 44 47 48 48 49 49