Having problems with Introspective Sort

Question

I'm trying to sort the arrays using different algorithms. Every algorithm that I use seems to work properly, however my IntroSort is behaving strangely. It's always slower than QuickSort and for large number of elements, for example million, it takes several minutes, when QuickSort takes approx. 1.2 seconds.

I tried to rewrite the code for introspective, heap and insertion sorts a couple of times with the same results. What can be the reason for this behaviour? Is there something wrong with my code?

The functions that I'm using (from file algorithms.h)

#pragma once

template <typename T>
void display_array(T* arr, int n) {     // displays full array in one line
    for (int i = 0; i < n; i++)
        std::cout << arr[i] << " ";
    std::cout << std::endl;
}

template <typename T>
void swap_values(T* x, T* y) {          // swaps two values
    T tmp = *x;
    *x = *y;
    *y = tmp;
}

/* * * * Quick Sort * * * */
template <typename T>
int quickS_part(T* arr, int left, int right) {
    int position = left;
    T pivot = arr[right];

    for (int i = left; i < right; i++) {
        if (arr[i] <= pivot) {
            swap_values(&arr[i], &arr[position]);
            position++;
        }
    }

    swap_values(&arr[position], &arr[right]);

    return position;
}

template <typename T>
void quick_sort(T* arr, int left, int right) {
    if (left < right) {
        int pivot = quickS_part(arr, left, right);

        quick_sort(arr, left, pivot - 1);
        quick_sort(arr, pivot + 1, right);
    }
}

/* * * * Heap Sort * * * */
template <typename T>
void heapify(T* arr, int size, int root) {
    int largest = root;
    int left = 2 * root + 1;
    int right = 2 * root + 2;

    if (left < size && arr[left] > arr[largest])
        largest = left;
    if (right < size && arr[right] > arr[largest])
        largest = right;

    if (largest != root) {
        swap_values(&arr[root], &arr[largest]);
        heapify(arr, size, largest);
    }
}

template <typename T>
void heap_sort(T* arr, int size) {
    for (int i = size / 2 - 1; i >= 0; i--)
        heapify(arr, size, i);

    for (int i = size - 1; i >= 0; i--) {
        swap_values(&arr[0], &arr[i]);
        heapify(arr, i, 0);
    }
}

/* * * * Insertion Sort * * * */
template <typename T>
void insertion_sort(T* arr, int left, int size) {
    for (int i = 1; i < size; i++) {
        T k = arr[i];
        int j = i - 1;
        while (k < arr[j] && j >= 0) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = k;
    }
}

/* * * * Introspective Sort * * * */
template <typename T>
void introS(T* arr, int left, int right, int maxdepth) {
    if ((right - left) < 16)
        insertion_sort(arr, left, right + 1);
    else if (maxdepth == 0)
        heap_sort(arr, right + 1);
    else {
        int pivot = quickS_part(arr, left, right);

        introS(arr, left, pivot - 1, maxdepth - 1);
        introS(arr, pivot + 1, right, maxdepth - 1);
    }
}

template <typename T>
void intro_sort(T* arr, int left, int right) {
    int md = 2 * floor(log(right + 1));
    introS(arr, left, right, md);
}

main.cpp:

#include <iostream>
#include <ctime>
#include <chrono>
#include <cmath>
#include "algorithms.h"

int main()
{
    //srand(time(NULL));

    const int size = 1000000;
    int *test1;
    test1 = new int[size];

    for (int i = 0; i < size; i++)
        test1[i] =  rand() % 1000000;

    auto start = std::chrono::high_resolution_clock::now();

    intro_sort(test1, 0, size - 1);

    auto end = std::chrono::high_resolution_clock::now();
    double time = std::chrono::duration<double, std::milli>(end - start).count();

    std::cout << "Sorting took " << time << " milliseconds." << std::endl;

    delete[] test1;
    return 0;
}

Answer 1

As it turnes out Heap Sort and Insert Sort are not implemented properly. I think what happens is that when they are called, they try to sort the whole array instead of the part of it.

This is the correct version that worked for me:

Insertion Sort:

template <typename T>
void insertion_sort(T* arr, int left, int size) {
    for (int i = left; i < size; i++) {
        T k = arr[i];
        int j = i - 1;
        while (k < arr[j] && j >= left) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = k;
    }
}

Heap Sort:

template <typename T>
void heap_sort(T* arr, int start, int size) {
    for (int i = size / 2 - 1; i >= start; i--)
        heapify(arr, size, i);                 // there are no changes in "heapify" function

    for (int i = size - 1; i >= start; i--) {
        swap_values(&arr[start], &arr[i]);
        heapify(arr, i, start);
    }
}

Introspective Sort:

template <typename T>
void introS(T* arr, int left, int right, int maxdepth) {
    if ((right - left) < 16)
        insertion_sort(arr, left, right + 1);
    else if (maxdepth == 0)
        heap_sort(arr, left, right + 1);
    else {
        int pivot = quickS_part(arr, left, right);

        introS(arr, left, pivot - 1, maxdepth - 1);
        introS(arr, pivot + 1, right, maxdepth - 1);
    }
}