Why is this heapsort code as slow as selection sort?

Question

I am doing a performance test on different sorting methods, and the Heapsort code from GeeksforGeeks is slower than the Selection sort. While it has a time complexity of O(n*logn), it seems to increase by a factor of 4, not 2.

The following table shows the elapsed time for each of the sorting methods. (from first column to last: Selection sort, Insertion sort, Merge sort, Quick sort, Heap sort)

elements  elapsed time
1,000     0.19   0.03   0.15    0.05    0.11
2,000     0.51   0.06   0.22    0.12    0.41
4,000     1.64   0.11   0.36    0.17    1.53
8,000     7.49   0.21   0.85    0.23    5.89
16,000    33.62  0.34   1.07    0.33    28.01
32,000    123.9  0.99   1.72    0.6    118.07

public class HeapSort 
{ 
    public void sort(int arr[]) 
    { 
        int n = arr.length; 

        for (int i = n / 2 - 1; i >= 0; i--) 
            heapify(arr, n, i); 
        for (int i=n-1; i>=0; i--) 
        { 
            int temp = arr[0]; 
            arr[0] = arr[i]; 
            arr[i] = temp; 
            heapify(arr, i, 0); 
        } 
    } 

    void heapify(int arr[], int n, int i) 
    { 
        int largest = i;
        int l = 2*i + 1; 
        int r = 2*i + 2; 
        if (l < n && arr[l] > arr[largest]) 
            largest = l;  
        if (r < n && arr[r] > arr[largest]) 
            largest = r; 
        if (largest != i) 
        { 
            int swap = arr[i]; 
            arr[i] = arr[largest]; 
            arr[largest] = swap;
            heapify(arr, n, largest); 
        } 
    }
}

public class SelectionSort_asc
{
    public static void sort(int[] a)
    {
        int n = a.length;

        for (int i = 0; i < n - 1; i++) // search all of the nums (except the last one)
        {
            int lowest = i; // index of the smallest number
            int lowkey = a[i]; // the smallest number

            for (int j = i + 1; j < n; j++)
            {
                if(a[j] < lowkey)
                {
                    lowest = j; // change the index of the smallest number
                    lowkey = a[j]; // value of the smallest number also changes
                }
            }
            int temp = a[i];
            a[i] = a[lowest];
            a[lowest] = temp; // swap a[i] and the smallest number found
        }
    }
}

Why is the speed so different from expected? Please give some help.

Answer 1

Example heapsort code. On my system, 32,000 elements doesn't take long enough, as display shows 0 milliseconds. 10,000,000 elements takes about 2 seconds. Using the selection sort you posted, 64,000 elements takes about 2.5 seconds; it's much slower.

package heapsort;
import java.util.Random;

public class heapsort {

    static void HeapSort(int[] a)
    {
    int end;
        Heapify(a);
        end = a.length-1;
        while(end > 0){
            int t = a[0];
            a[0] = a[end];
            a[end] = t;
            end--;
            SiftDown(a, 0, end);
        }
    }

    static void Heapify(int[] a)
    {
    int root;
        if(a.length < 2)
            return;
        root = (a.length - 2) / 2;
        while(true){
            SiftDown(a, root, a.length-1);
            if(root == 0)
                break;
            root--;
        }
    }

    static void SiftDown(int[] a, int root, int end){
    int parent;
    int child;
    int t;
        for(parent = root; (child = parent * 2 + 2) <= end; ){
            if(a[child-1] > a[child])
                child = child-1;
            if(a[child] > a[parent]){
                t = a[child];
                a[child] = a[parent];
                a[parent] = t;
                parent = child;
            } else {
                break;
            }
        }
        if((child = parent * 2 + 1) <= end){
            if(a[child] > a[parent]){
                t = a[child];
                a[child] = a[parent];
                a[parent] = t;
            }
        }
    }

    public static void main(String[] args) {
        int[] a = new int[32000];
        Random r = new Random();
        for(int i = 0; i < a.length; i++)
            a[i] = r.nextInt();
        long bgn, end;
        bgn = System.currentTimeMillis();
        HeapSort(a);
        end = System.currentTimeMillis();
        for(int i = 1; i < a.length; i++){
            if(a[i-1] > a[i]){
                System.out.println("failed");
                break;
            }
        }
        System.out.println("milliseconds " + (end-bgn));
    }
}