MAG MAG - 5 months ago 16
Java Question

Merge Sort most efficient implementation

So I wonder what is the most efficient implementation of a merge sort in Java (In case its efficiency in terms of time can change depending on the language). This question may be trivial but my ultimate goal is to learn from more experienced programmers. Here are 2 examples I made:

//version I made.
public static double[] mergeSort(double[] arreglo) {
if (arreglo.length > 1) {
int d = (arreglo.length / 2);
double[] arreglo1 = Arrays.copyOfRange(arreglo, 0, d),
arreglo2 = Arrays.copyOfRange(arreglo, d, arreglo.length);
arreglo1 = mergeSort(arreglo1);
arreglo2 = mergeSort(arreglo2);
return merge(arreglo1, arreglo2);
} else {
return arreglo;
}
}

public static double[] merge(double[] arreglo1, double[] arreglo2) {
double[] convi = new double[arreglo1.length + arreglo2.length];
for (int i = 0, m1 = 0, m2 = 0; i < convi.length; i++) {
if (arreglo1.length > m1 && arreglo2.length > m2) {
if (arreglo1[m1] <= arreglo2[m2])
convi[i] = arreglo1[m1++];
else {
convi[i] = arreglo2[m2++];
}
} else {
convi[i] = (arreglo1.length == m1) ? arreglo2[m2++] : arreglo1[m1++];
}
}
return convi;
}

//Taken out of Cormens book.
public static void mergeSort(int[] arreglo, int i, int f) {
if (f > i) {
int d = ((i + f) / 2);
mergeSort(arreglo, i, d);
mergeSort(arreglo, d + 1, f);
merge(arreglo, i, d, f);
}
}


public static void merge(int[] arreglo, int i, int m, int f) {
int n1 = (m - i) + 1;
int n2 = (f - m);
int[] mitad1 = new int[n1 + 1];
int[] mitad2 = new int[n2 + 1];
for (int v = 0; v < n1; v++) {
mitad1[v] = arreglo[i + v];
}
for (int p = 0; p < n2; p++) {
mitad2[p] = arreglo[p + m + 1];
}
mitad1[n1] = Integer.MAX_VALUE;
mitad2[n2] = Integer.MAX_VALUE;
for (int r = i, m1 = 0, m2 = 0; r <= f; r++) {
if (mitad1[m1] <= mitad2[m2]) {
arreglo[r] = mitad1[m1];
m1++;
} else {
arreglo[r] = mitad2[m2];
m2++;
}
}
}

Answer

The following program is translated from C++ example given in Robert Sedgewick's Algorithms in C++, Parts 1-4

It introduces one type of improvement. It does a single copy of the whole sorting array into a an auxiliary array that is further dealt with. Next, the recursion splitting is done on the auxiliary array by alternating between the auxiliary array and original array so that the extra copying operation of the merged arrays doesn’t happen. Basically, the algorithm switches the role of the input and auxiliary array in each recursive call. For example, conceptually:

Regular Mergesort:

--merge

(((8) (5))((2) (3)))(((1) (7))((4) (6)))

(( 5 8 )( 2 3 ))(( 1 7 )( 4 6 ))

-- copy back and ignore previous (UNNECESSARY)

(( 5 8 )( 2 3 ))(( 1 7 )( 4 6 ))

– – – – – – – –

This program:

--merge

(((8) (5))((2) (3)))(((1) (7))((4) (6)))

(( 5 8 )( 2 3 ))(( 1 7 )( 4 6 ))

--merge backwards

( 2 3 5 8 )( 1 4 6 7 )

(( 5 8 )( 2 3 ))(( 1 7 )( 4 6 ))    

Also, after splitting the array into halves gives small enough arrays, the algorithm uses insertion sort since it performs better on small data sets than merge sort. The threshold for when exactly to use insertion sort can be determined with trial-and-error.

The code:

static int M = 10;

//insertion sort to be used once the mergesort partitions become small enough
static void insertionsort(int[] a, int l, int r) {
    int i, j, temp;
    for (i = 1; i < r + 1; i++) {
        temp = a[i];
        j = i;
        while ((j > 0) && a[j - 1] > temp) 
        {
            a[j] = a[j - 1];
            j = j - 1;
        }
        a[j] = temp;
    }
}

//standard merging two sorted half arrays into single sorted array
static void merge(int[] merged_a, int start_a, int[] half_a1, int start_a1, int size_a1, 
                         int[] half_a2, int start_a2, int size_a2) {
    int i, j, k;
    int total_s = size_a1 + size_a2;
    for (i = start_a1, j = start_a2, k = start_a; k < (total_s); k++) {
        // if reached end of first half array, run through the loop 
        // filling in only from the second half array
        if (i == size_a1) {
            merged_a[k] = half_a2[j++];
            continue;
        }
        // if reached end of second half array, run through the loop 
        // filling in only from the first half array
        if (j == size_a2) {
            merged_a[k] = half_a1[i++];
            continue;
        }
        // merged array is filled with the smaller element of the two 
        // arrays, in order
        merged_a[k] = half_a1[i] < half_a2[j] ?
                      half_a1[i++] : half_a2[j++];
    }
}

//merge sort data during merging without the additional copying back to array
//all data movement is done during the course of the merges
static void mergesortNoCopy(int[] a, int[] b, int l, int r) {
    if (r - l <= M) {
        insertionsort(a + l, l, r - l);
        return;
    }
    int m = (l + r) / 2;
    //switch arrays to msort b thus recursively writing results to b
    mergesortNoCopy(b, a, l, m); //merge sort left
    mergesortNoCopy(b, a, m + 1, r); //merge sort right
    //merge partitions of b into a
    merge(a, l, b, l, m - l + 1, b, m + 1, r - m); //merge
}

static void mergesort(int[] a) {
    int[] aux = Arrays.copyOf(a, a.length);
    mergesortNoCopy(a, aux, 0, a.length - 1);
}

Some other possible improvements:

Stop if already sorted.

Check if the largest item in first half ≤ smallest item in second half. Helps for partially-ordered arrays.

// after split, before merge
if (a[mid] <= a[mid + 1]) return;

EDIT: here is a good document I found on different versions of Mergesort and improvements thereof.

Comments