What is the best implementation of 'Mergesort Algorithm'?

Asked

Viewed 1,224 times

6

I know the Quick Sort algorithm, but at the moment I want to analyze Merge Sort.

I found two types of Merge Sort implementation on the Internet. 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

There is another way to implement Merge Sort to make it more efficient than the Insertion 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");

    }
}

--- and ---

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

}
  • I think the first point is that a single round is not a good parameter. Who knows how to run 20 times and take the average is standard deviation? I also don’t think it’s interesting to run based on a single starting situation. Finally, you only have 501 distinct items (or would it be 500? , if starting from 1?), the insertion algorithm is optimal when there is partial ordering (up to o(n) in the best case), mergesort will always execute o(n log n) instructions

  • My conclusion is that I see more problematic research methodology than algorithm itself

  • There’s a spot I picked up on merge2: the extra memory size of mergesort is n + o(log n) + o(1). Note that part is constant, because you need an auxiliary vector in the algorithm, not an auxiliary vector for each function call merge2. Another point that helps is that you always pass the two vectors, alternating who is the main vector and who is the secondary in recursion.

  • Okay @Jefferson Quesado! I’ll follow your lead. Thank you!

  • I made a small model to do the math. Just picking up here your sorting implementations to test and see if the times are compatible

  • What test environment? I’m on my 2.4GHz i7 laptop and, running 100 times bubblesort, I got the accumulated total time of 310 seconds

  • I am creating a repository to make it easier to follow what is being done: https://gitlab.com/totalcross/stack-overflow/tree/master/performance-sort; when finished, I put the relevant parts in the answer

Show 2 more comments

1 answer

6


TL;DR

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

Look at 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

Calmly solving the issue

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

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

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

You can access the test repository on Gitlab.

I divided the code into 3 parts to clarify each responsibility:

Sortstuff.java

This guy here has the function of calling the sorter and collecting the data by sending to the statistical calculations part 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 little bit of Java 8 English expressions to decrease how much code I’ve produced.

The function main makes the call to repeatGetEstatisticas. In this case, it configures which sort strategy will be used to measure 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 sorting methods were made in such a way that they have no explicit arguments, and have no return. Then, they behave as if they were a function that simply consumes the object containing the vector to be ordered. Remember, the this that we mention within an instance method is an implicit argument passed to the method. To simulate the method call of that object, I metodoOrdenacao.accept(a).

The function repeatGetEstatisticas ago n times the past operation. The past operation is a function that, when executed, generates a long as a result, it is immediately passed to the class responsible for the statistical calculations. Your output is exactly that set of data produced.

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

Statistics.

Do the statistical calculations. Nothing interesting, pure boredom.

Java array.

Class containing the vector to be ordered v, your 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 have chosen Random.nextInt(int bound), which generates a uniform distribution in the range [0, bound), however, as the quantity of requested elements was much greater than this limit, there was a lot of repetition within 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 objects in memory can generate very positive results, especially when the expected amount of additional objects created is o(n) (with average size of o(log n) each) for an algorithm whose execution time is o(n log n).

Nor was it necessary to make a copy of the areaTrabalho back to entradaDesordenada, what saves o(n) operations for each method call merge*, that will join the two ordered vector halves into a single part.

Another small optimization that I did, but I didn’t go after studying the side effect, was to call the call System from Java to copy vectors: System.arraycopy(v, 0, aux, 0, n);. Supposedly, calling it that offers much more efficient performance than manually copying by a loop.

Phallus supposedly because in fact I have not measured the time. If I am not mistaken, this call System.arrayCopy makes a call internally to the function memcpy of (described in string.h), or the processor command for copying memory regions

Completion

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

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

I also decided to take one last cruel doubt, how would the behavior of the other mergesorts be if the set increased in size? So I ran the test for 100,000 elements, five 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, the old mergesorts are now taking "only" 2x the insertionsort time; when they were 30,000 elements, they were 3x longer, an indication that with the input size, even the not optimized mergesorts may be better than the insertionsort.

Another interesting point is that the insertionsort presented a very high standard deviation, about 67% of the average size. This, to me, indicates that the insertionsort was not tested enough, few sets of work were collected for it. You would need to repeat the test 100 times or more to see if your behavior would converge to some less inaccurate value.

Browser other questions tagged

You are not signed in. Login or sign up in order to post.