Heapsort vs std::sort / Arrays.sort()

heapsortCPP.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <ctime>

const long N = 2000000000;
using namespace std;

void heapify(vector<int> & heap, int i, int heapsize)
{
    int left = 2*(i) + 1;
    int right = 2*(i) + 2;
    int largest;
    if (left < heapsize && heap[left] > heap[i])
    {
        largest = left;
    }
    else
    {
        largest = i;
    }
        
    if (right < heapsize && heap[right] > heap[largest])
    {
        largest = right;
    }
        
    if (largest != i)
    {
        int tmp = heap[i];
        heap[i] = heap[largest];
        heap[largest] = tmp;
         
        heapify(heap, largest, heapsize);
    }
}

void buildHeap(vector<int> & heap, int heapsize)
{
    for(int i = heapsize/2;i >= 0;i--)
    {
        heapify(heap, i, heapsize);
    }
}

void heapSort(vector<int> & heap, int length)
{
    int heapsize = length;
    buildHeap(heap, heapsize);
    for(int i = heapsize-1; i >= 1; i--)
    {
        int tmp = heap[0];
        heap[i] = heap[0];
        heap[i] = tmp;
        heapsize--;
        heapify(heap, 0, heapsize);
    }
}
    
int randomval()
{
	double d;
    int result;
    d = rand() / RAND_MAX;
    result = (int) (d * N);
    return result;
}

bool isSorted(vector<int> & a, int length) {
        for (unsigned int i = 0; i < a.size() - 1; i++) {
            if (a[i] > a[i + 1]) {
                return false;
            }
        }
        return true;
    }

int main()
{
	int length = 100000000;
	vector<int> vint;
	srand((unsigned)time(0)); 
	for (int i = 0; i < length; i++)
	{
        vint.push_back(randomval());
	}

	clock_t startTime = clock();
	heapSort(vint,vint.size());
    float secsElapsed = (float)(clock() - startTime)/CLOCKS_PER_SEC;

    cout << "Heapsort: " << secsElapsed << endl;
    cout << isSorted(vint, length) << endl << endl;

    vint.clear();
    for (int i = 0; i < length; i++)
    {
        vint.push_back(randomval());
    }
    
    startTime = clock();
    sort(vint.begin(), vint.end());
    secsElapsed = (float)(clock() - startTime)/CLOCKS_PER_SEC;

    cout << "std::sort: " << secsElapsed << endl;
    cout << isSorted(vint, length) << endl;
}

JavaHeapsort.java

package sorttest;

public class HeapSort {
    static void heapSort(int [] heap){
        int heapsize = heap.length;
        buildHeap(heap, heapsize);
        for (int i = heapsize-1; i >= 1; i--){
            int tmp = heap[0];
            heap[i] = heap[0];
            heap[i] = tmp;
            heapsize--;
            heapify(heap, 0, heapsize);
        }
    }
    
    private static void buildHeap(int [] heap, int heapsize){
        for(int i = heapsize/2;i >= 0;i--){
            heapify(heap, i, heapsize);
        }
    }
    
    private static void heapify(int [] heap, int i, int heapsize){
        int left = 2*(i) + 1;
        int right = 2*(i) + 2;
        int largest;
        if (left < heapsize && heap[left] > heap[i]){
            largest = left;
        }
        else{
            largest = i;
        }
        
        if (right < heapsize && heap[right] > heap[largest]){
            largest = right;
        }
        
        if (largest != i){
            int tmp = heap[i];
            heap[i] = heap[largest];
            heap[largest] = tmp;
            
            heapify(heap, largest, heapsize);
        }
    }
}

JavaMain.java

package sorttest;

import java.util.Random;
import java.util.Arrays;

public class Main {

    public static void main(String[] args) {
        
        final int size = 100000000;
        int[] array = new int[size];
        System.out.println("Starting random generation");
        Random random = new Random();
        for (int i = 0; i < size; i++) {
            array[i] = random.nextInt(2000000000);
        }
        System.out.println("Sorting started");

        long currenttime = System.currentTimeMillis();
        Arrays.sort(array);
        System.out.println("Arrays.sort time: " + (double) (System.currentTimeMillis() - currenttime) /1000 + " seconds.");
        System.out.println("Is sorted: " + isSorted(array));
        
        for (int i = 0; i < size; i++) {
            array[i] = random.nextInt(2000000000);
        }
        
        currenttime = System.currentTimeMillis();
        HeapSort.heapSort(array);
        System.out.println("Heap sort time: " + (double) (System.currentTimeMillis() - currenttime) /1000 + " seconds.");
        System.out.println("Is sorted: " + isSorted(array));
        
        
        
    }

    static Boolean isSorted(int[] heap) {
        for (int i = 0; i < heap.length - 1; i++) {
            if (heap[i] > heap[i + 1]) {
                return false;
            }
        }
        return true;
    }
}