Merge Sort vs Selection Sort

Question

I have written these 2 sorting algorithms and it appears that selection sort is faster than merge sort, surely this can't be right? My test data is 10 random arrays of size 5000 to 50000 where the largest possible numbers in the array is 100.

Here is my selection sort implementation:

int i, j, iMin;
int n = c.length;

startTime = System.currentTimeMillis();
for (i = 0; i < n - 1; i++) {
    iMin = i;
    for (j = i + 1; j < n; j++)
        if (c[j] < c[iMin]) {
            iMin = j;
            if (sorting) {
                theDelay();
            }
        }

    if (iMin != i) {
        swap(c, iMin, i);
        if (sorting) {
            theDelay();
        }
    }
}
endTime = System.currentTimeMillis();
overallTime = endTime - startTime;
// System.out.println(overallTime);

The theDelay() method is simply to delay the thread that the sorting algorithm runs within so that a visual graph can draw to the JPanel to show the sort in action, in this test case it is being ignored so wont affect my sort time.

Here is my merge sort implementation:

public void mergeSort(int[] d) throws InterruptedException {
    startTime = System.currentTimeMillis();
    MergeSort(d, 0, d.length - 1);
    endTime = System.currentTimeMillis();
    overallTime = endTime - startTime;
    //System.out.println("Merge" +overallTime);
}

private void MergeSort(int[] array, int low, int high) throws InterruptedException {
    int[] temp = new int[array.length];
    if (low < high) {
        int middle = low + (high - low) / 2;
        MergeSort(array, low, middle);
        MergeSort(array, middle + 1, high);
        ReMerge(array, temp, low, middle, high);
    }
}

private void ReMerge(int[] array2, int[] temp, int low, int middle, int high) throws InterruptedException {
    for (int i = low; i <= high; i++) {
        temp[i] = array2[i];
    }
    int i = low;
    int j = middle + 1;
    int k = low;

    while (i <= middle && j <= high) {
        if (temp[i] <= temp[j]) {
            array2[k] = temp[i];
            i++;
            if (sorting) {
                theDelay();
            }
        } else {
            array2[k] = temp[j];
            j++;
            if (sorting) {
                theDelay();
            }
        }
        k++;
    }
    while (i <= middle) {
        array2[k] = temp[i];
        k++;
        i++;
        if (sorting) {
            theDelay();
        }
    }
}

is there something in my implementation affecting the time it should take for a merge sort to complete???

Answer 1

You have:

private void MergeSort(int[] array, int low, int high) throws InterruptedException
{
    int[] temp = new int[array.length];

Of course allocating an array of length 5000 to 50000 at each step of the recursion will make the algorithm much slower. Try to reuse the same temp array.