What is the best implementation of the 'MergeSort algorithm'?

I know the quick Sort algorithm, but at the moment I want to parse the Merge Sort.

I found on the internet two types of Merge Sort implementation. But when I compare them to the insertion algorithm, they seem to be less efficient and this is not expected for a large number of items.

Enter the number of elements you want to sort:
300000

Time spent to executing BubbleSort: 362123 milliseconds
Time spent to executing Selection:  108285 milliseconds
Time spent to executing Insertion:   18046 milliseconds
Time spent to executing MergeSort:   35968 milliseconds
Time spent to executing MergeSort2:  35823 milliseconds

Have another way to implement Merge Sort to make it more efficient than the Insert algorithm ?

Look at my code...

package br.com.test.test1;

import java.util.Random;
import java.util.Scanner;

 /**
 *
 * @author Joao
 */
public class Main {

    // generate an int array with random numbers between 0 and 500
    public static int[] generateRand(int n){
        int[] randArray = new int[n];
        Random number = new Random();

        // random numbers between 0 and 500
        for (int i = 0; i < n; i++){
            randArray[i] = number.nextInt(501);
        }
        return randArray;
    }

    public static void main(String[] args) {
        long startTime;
        Scanner input = new Scanner(System.in);
        int n;

        System.out.println("Enter the number of elements you want to sort:");
        n = input.nextInt();

        MyArray array = new MyArray(n);
        int[] aux = new int[n];
        aux = generateRand(n);


        array.copy(aux);   
        startTime = System.currentTimeMillis();
        array.bubblesort();
        // Time spent to executing BUBBLESORT 
        System.out.println("\nTime spent to executing BubbleSort: "+(System.currentTimeMillis() - startTime)+" milliseconds");


        array.copy(aux);   
        startTime = System.currentTimeMillis();
        array.selection();
        // Time spent to executing SELECTION 
        System.out.println("Time spent to executing Selection: "+(System.currentTimeMillis() - startTime)+" milliseconds");


        array.copy(aux);   
        startTime = System.currentTimeMillis();
        array.insertion();
        // Time spent to executing INSERTION 
        System.out.println("Time spent to executing Insertion: "+(System.currentTimeMillis() - startTime)+" milliseconds");


        array.copy(aux);   
        startTime = System.currentTimeMillis();
        array.mergeSort(0, n-1);
        // Time spent to executing MERGESORT 
        System.out.println("Time spent to executing MergeSort: "+(System.currentTimeMillis() - startTime)+" milliseconds");


        array.copy(aux);   
        startTime = System.currentTimeMillis();
        array.mergeSort2(0, n-1);
        // Time spent to executing MERGESORT 2
        System.out.println("Time spent to executing MergeSort2: "+(System.currentTimeMillis() - startTime)+" milliseconds");

    }
}

- - - e - - - 

package br.com.test.test1;

/**
 *
 * @author Joao Paulo
 */
class MyArray {
    private int[] v;
    private int n;  // array index
    private int len;

    public MyArray(int length) {
        len = length;
        v = new int[len];
        n = 0;
    }

    public void copy(int[] k){
        n = 0;
        for (int i = 0; i < len; i++) {
            v[i] = k[i];
            n++;
        }
    }

    public void show(){
        for (int i = 0; i < n; i++) {
            System.out.print(" " + v[i]);
        }
        System.out.println("\n");
    }


    // *******  START OF ALGORITHMS TO SORT  *******

    // ----------   Start of BubbleSort and Selection   --------------
    public void bubblesort(){
        for (int i = 0; i < n; i++){
            for (int j = 0; j < n-1; j++) {
                if (v[j] > v[j+1]) {
                    change(j, j+1);
                }
            }
        }
    }

    public void selection() {
        int min;
        for (int i = 0; i < n-1; i++) {
            min = i;
            for (int j = i+1; j < n; j++){
                if (v[j] < v[min]){
                    min = j;
                }
            }
            change(i, min);
        }
    }

    private void change(int one, int two) {
        int temp = v[one];
        v[one] = v[two];
        v[two] = temp;
    }
    // ----------   End of BubbleSort and Selection   ----------------


    // ----------   Start of Insertion   -----------------------------
    public void insertion() {
        int i, j;
        int temp;
        for (i=1; i < n; i++) {
            temp = v[i];   // marked variable
            j = i;
            while ((j > 0) && (v[j-1] > temp)) {
                v[j] = v[j-1];
                j = j - 1;
            }
            v[j] = temp;
        }
    }
    // ----------   End of Insertion   -------------------------------


    // ----------   Start of MergeSort   -----------------------------
    public void mergeSort (int start, int end){
        if(start == end) return;

        int middle = (start+end)/2;
        mergeSort(start,middle);
        mergeSort(middle+1,end);
        merge(start,middle,end);
    }

    public void merge(int start, int middle, int end) {
        int[] aux = new int[v.length];

        for (int x = start; x <= end; x++) {
            aux[x] = v[x];
        }

        int i = start;
        int j = middle+1;
        int k = start;

        //emptying out array 'v' inserting items neatly in array 'aux' 
        while (i <= middle && j <= end) {
            if (aux[i] < aux[j]){
                v[k++] = aux[i++];
            } else {
                v[k++] = aux[j++];
            }
        }

        //copying values from 'aux' to 'v'
        while (i <= middle){
            v[k++] = aux[i++];
        }

        while (j <= end){
            v[k++] = aux[j++];
        }
    }
    // ----------   End of MergeSort   -------------------------------


    // ----------   Start of MergeSort 2  ----------------------------
    public void mergeSort2 (int start, int end) {
        if(start >= end) return;

        int middle = (start+end)/2;
        mergeSort2(start,middle);
        mergeSort2(middle+1,end);
        merge2(start,middle,end);
    }

    public void merge2(int start, int middle, int end) {
        int[] helper = new int[v.length];

        // Copy both parts into the helper array
        for (int i = start; i <= end; i++) {
            helper[i] = v[i];
        }

        int i = start;
        int j = middle + 1;
        int k = start;

        // Copy the smallest values from either the left or the right side back to the original array
        while (i <= middle && j <= end) {
            if (helper[i] <= helper[j]) {
                v[k] = helper[i];
                i++;
            } else {
                v[k] = helper[j];
                j++;
            }
            k++;
        }

        // Copy the rest of the left side of the array into the target array
        while (i <= middle) {
            v[k] = helper[i];
            k++;
            i++;
        }
        // Since we are sorting in-place any leftover elements from the right side
        // are already at the right position.
    }
    // ----------   End of MergeSort 2  ------------------------------

}
Author: João Paulo Rolim, 2017-09-08
Source

1 answers

TL; DR

I optimized the creation of the working auxiliary vector and the expected time to run merge sort v3 is 4.29 ms +- 0.78 ms

See the data I got: 

Repetições do experimento de BUBBLE SORT: 100
Total acumulado de BUBBLE SORT: 241062
Média de BUBBLE SORT: 2410.62
Desvio padrão de BUBBLE SORT: 235.99742251631358
Repetições do experimento de BUBBLE SORT MINIMO: 100
Total acumulado de BUBBLE SORT MINIMO: 163971
Média de BUBBLE SORT MINIMO: 1639.71
Desvio padrão de BUBBLE SORT MINIMO: 36.23835096700842
Repetições do experimento de BUBBLE SORT FLAGGED: 100
Total acumulado de BUBBLE SORT FLAGGED: 169241
Média de BUBBLE SORT FLAGGED: 1692.41
Desvio padrão de BUBBLE SORT FLAGGED: 51.61025170262282
Repetições do experimento de SELECTION SORT: 100
Total acumulado de SELECTION SORT: 35973
Média de SELECTION SORT: 359.73
Desvio padrão de SELECTION SORT: 13.946401729913024
Repetições do experimento de INSERTION SORT: 100
Total acumulado de INSERTION SORT: 11862
Média de INSERTION SORT: 118.62
Desvio padrão de INSERTION SORT: 57.24637168159279
Repetições do experimento de MERGE SORT: 100
Total acumulado de MERGE SORT: 33125
Média de MERGE SORT: 331.25
Desvio padrão de MERGE SORT: 30.73785380545715
Repetições do experimento de MERGE SORT (2): 100
Total acumulado de MERGE SORT (2): 32395
Média de MERGE SORT (2): 323.95
Desvio padrão de MERGE SORT (2): 11.65703065263035
Repetições do experimento de MERGE SORT (3): 100
Total acumulado de MERGE SORT (3): 429
Média de MERGE SORT (3): 4.29
Desvio padrão de MERGE SORT (3): 0.782317200386264

Solving the question calmly

I performed the test with its 5 sorting algorithms plus the following others that I put:

  1. minimal bubblesort (each iteration in the outer loop ensures that the largest element in the unordered part stays in its correct position, not needing be rechecked)
  2. minimal bubblesort with flag (similar to minimum, but has a flag to detect if there has been any change; if not, the vector is ordered and we can stop)
  3. mergesort with a single memory allocation (I ended up picking up the implementation available in Wikipedia, top-down version)

To ensure the test results, every vector that would be ordered was initialized in a totally random manner, with numbers evenly distributed in the domain of integers with 32-bit signal ([-2^31, 2^31 - 1]). I ran the test 100 times and collected the data to do the mean, total sum and standard deviation.

You can access the test repository in GitLab.

I divided into 3 parts the code to be clearer each responsibility:

SortStuff.java

This guy here has the function of calling the computer and collecting the data, sending to the part of statistical calculations each round: 

package sort;

import java.util.function.Consumer;
import java.util.function.LongSupplier;

public class SortStuff {
    public static final int SIZE_ARRAY = 30_000;
    public static final int N_REPETITION = 100;

    public static LongSupplier calculaTempo(Consumer<Array> metodoOrdenacao) {
        return () -> {
            Array a = Array.getRandomArray(SIZE_ARRAY);

            long init = System.currentTimeMillis();
            metodoOrdenacao.accept(a);
            return System.currentTimeMillis() - init;
        };
    }

    public static void main(String[] args) {
        Estatisticas estatBubble = repeatGetEstatisticas(N_REPETITION, calculaTempo(Array::bubbleSort));
        Estatisticas.printEstatisticas(estatBubble, "BUBBLE SORT");

        Estatisticas estatBubble2 = repeatGetEstatisticas(N_REPETITION, calculaTempo(Array::bubbleSort2));
        Estatisticas.printEstatisticas(estatBubble2, "BUBBLE SORT MINIMO");

        [...] /* basicamente a mesma coisa para as outras estratégias de ordenação */

        Estatisticas estatMerge3 = repeatGetEstatisticas(N_REPETITION, calculaTempo(Array::mergeSort3));
        Estatisticas.printEstatisticas(estatMerge3, "MERGE SORT (3)");
    }

    private static Estatisticas repeatGetEstatisticas(int n, LongSupplier l) {
        Estatisticas estat = new Estatisticas();
        for (int i = 0; i < n; i++) {
            estat.adicionaRodada(l.getAsLong());
            System.err.println("Terminou a rodada " + i);
        }

        return estat;
    }

}

Note that I'm using a bit of Java 8 lambdas expressions to decrease how much code I've produced.

The function main makes the call to the repeatGetEstatisticas. In this case, it configures which sort strategy will be used to measure the time.

In function calculaTempo, given one of the chosen sorting methods, returns another function that counts the time needed to do only the sorting time. The ordering methods were made of such luck that they have no explicit arguments, and they have no return. So they behave as if they were a function that simply consumes the object containing the vector to be ordered. Remember, the this we mention inside an instance method is an implicit argument passed to the method. To simulate the method call of that object, I did metodoOrdenacao.accept(a).

The function repeatGetEstatisticas does n times the operation passed. The past operation is a function that, by being executed, generates a long as a result, which is immediately passed to the class responsible for the statistical calculations. Its output is exactly that set of data produced.

Note that calculaTempo generates a function that returns the time required in milli seconds to be used in repeatGetEstatisticas.

Statistics.java

Does the statistical calculations. Nothing interesting, pure boredom.

Array.java

Class containing the vector to be ordered v, its size n and sorting methods. I also made a random initializer by passing the vector size, the static method Array.getRandomArray.

public static Array getRandomArray(int n) {
    Array a = new Array(n);

    Random number = new Random();

    for (int i = 0; i < n; i++) {
        // Random.nextInt() é, pelo que li, uniforme em todo o domínio
        // inteiro 32 bits
        a.v[i] = number.nextInt();
    }

    return a;
}

The only relevant difference between our two random initializations was that I choose Random.nextInt(), which generates for the domain of integers a uniform distribution. You chose Random.nextInt(int bound), which generates a uniform distribution in the range [0, bound), but since the amount of elements requested was much greater than this limit, there was a lot of repetition inside the vector.

The other interesting point is the third mergesort option I wrote (based on the Wikipedia entry, as mentioned above): 

public void mergeSort3() {
    // cria o vetor auxiliar uma única vez
    int aux[] = new int[n];

    System.arraycopy(v, 0, aux, 0, n);

    mergeSort3(aux, v, 0, n);
}

/**
 * ordenar o vetor no intervalo [ini,end), fechado no começo e aberto no
 * final
 * 
 * areaTrabalho vai carregar o etor ordenado, no final
 * 
 * @param entradaDesordenada
 *            vetor de entrada, não prometo alterar
 * @param areaTrabalho
 *            local onde vai acontecer o trabalho de ordenação das
 *            informações da entradaDesordenada
 * @param ini
 * @param end
 */
private void mergeSort3(int[] entradaDesordenada, int[] areaTrabalho, int ini, int end) {
    if (end - ini <= 1) {
        return;
    }

    int middle = (ini + end) / 2;
    mergeSort3(areaTrabalho, entradaDesordenada, ini, middle);
    mergeSort3(areaTrabalho, entradaDesordenada, middle, end);
    merge3(entradaDesordenada, areaTrabalho, ini, middle, end);
}

public void merge3(int[] entradaDesordenada, int[] areaTrabalho, int start, int middle, int end) {
    int i = start;
    int j = middle;

    for (int k = start; k < end; k++) {
        if (i < middle && (j >= end || entradaDesordenada[i] <= entradaDesordenada[j])) {
            areaTrabalho[k] = entradaDesordenada[i];
            i++;
        } else {
            areaTrabalho[k] = entradaDesordenada[j];
            j++;
        }
    }
}

Note that there is only one call to the operator new int[]. This means that the auxiliary vector is only created once. Avoiding creating in-memory objects can yield very positive results, even more so when the expected amount of additional objects created is o(n) (with an average size of o(log n) each) for a algorithm whose runtime is o(n log n).

It was also not necessary to copy the areaTrabalho back to entradaDesordenada, which saves o(n) operations for each merge* method call, which will join the two ordered halves of the vector into a single part.

Another small optimization that I did, but did not go after studying the side effect, was to call the Java call System to copy vectors: System.arraycopy(v, 0, aux, 0, n);. Supposedly, calling like this offers a very more efficient than copying done manually by a loop.

I speak supposedly because in fact I did not measure time. If I'm not mistaken, this System.arrayCopy call makes an internal call to the memcpy function of c (described in string.h), or to the processor command for copying memory regions

Conclusion

Analyzing the Times, proportionally they are kind of consistent with the results you got (only the selectionsort that fared proportionally better over insertionsort). So my hypothesis that I put in the comments of possible failure in the evaluation methodology was falsified. I apologize: -)

Taking the memory allocation factor out, mergesort time was about 25 times faster than insertionsort time for 30,000 elements. Compared to the other mergesort alternatives you had put, it was 75 times faster.

I also solved take one last cruel doubt, how would the behavior of the other mergesorts be if the set increased in size? So I did the test for 100,000 elements, 5 rounds: 

Repetições do experimento de INSERTION SORT: 5
Total acumulado de INSERTION SORT: 13589
Média de INSERTION SORT: 2717.8
Desvio padrão de INSERTION SORT: 1937.7354566606869
Repetições do experimento de MERGE SORT: 5
Total acumulado de MERGE SORT: 21585
Média de MERGE SORT: 4317.0
Desvio padrão de MERGE SORT: 98.35903618885253
Repetições do experimento de MERGE SORT (2): 5
Total acumulado de MERGE SORT (2): 23670
Média de MERGE SORT (2): 4734.0
Desvio padrão de MERGE SORT (2): 334.4233843498388
Repetições do experimento de MERGE SORT (3): 5
Total acumulado de MERGE SORT (3): 108
Média de MERGE SORT (3): 21.6
Desvio padrão de MERGE SORT (3): 1.6733200530681511

Note that, on average, old mergesorts are now taking "only" 2x the time of insertionsort; when it was 30,000 elements, it was 3x longer, an indication that with the size of the input, even unoptimized mergesorts can be better than insertionsort.

Other point interestingly, insertionsort showed a very high standard deviation, about 67% of the average size. This, to me, indicates that insertionsort has not been tested enough, few working sets have been collected for it. You would need to repeat the test about 100 times or more to see if your behavior would converge to some less inaccurate value.

 6
Author: Jefferson Quesado, 2020-03-28 18:24:52