The fastest number sorting algorithm

Better is the sight of the eyes than the wandering of the desire: this is also vanity and vexation of spirit.

Ecclesiastes 6:9

Years ago, I had the idea to create perhaps the fastest algorithm for sorting integers. After about a month of thinking and testing, I managed to create a working sorting program in the C++ language. The current version has the following features:

• Sorts unordered whole numbers in the range 0 to 100000000.
• It has a linear complexity O(n).
• Space complexity Not In-place O(n).
• Unstable sorting algorithm.
• Internal sort algorithm.
• Iterative algorithm.

I tested it on Intel Xeon CPU E5-2680 v2 at 2.80Ghz with a total memory of 4 GB. Sorting time is four seconds to sort an array of two hundred million units. The algorithm needs improvements. I ask for your comments and recommendations!

Sample code of the fastest algorithm for sorting positive integers

#include <iostream>
#include <algorithm>
#include <time.h>

using namespace std;

void pause() {
    cout << "Press Enter key to continue.";
    cin.ignore().get();
}

int main () {
    srand(time(NULL));
    if (sizeof(int) >= 4) {
        int random_array_length, sorted_array_length, n, zeros = 0, i = 0;
        cout << "Enter random numbers array length up to 100000000" << endl;
        cin >> random_array_length;
        if (random_array_length < 2 or random_array_length > 100000000) {
            cout << "Number is out of range!";
            return 1;
        }
        int *array = new int[random_array_length];
        int *random_array = new int[random_array_length];
        for (n = 0; n < random_array_length; ++n) {
            random_array[n] = rand() % random_array_length;
            array[random_array[n]] = random_array[n];
        }
        cout << endl;
        int smallest = *min_element(random_array, random_array + random_array_length);
        int largest = *max_element(random_array, random_array + random_array_length);
        cout << "The smallest number is " << smallest << endl;
        cout << "The largest number is "  << largest << endl;
        pause();
        clock_t tStart = clock();
        for (n = smallest; n < largest + 1; ++n) {
            zeros = (array[n] == 0) ? zeros += 1 : zeros;
        }
        zeros = (smallest == 0) ? zeros -= 1 : zeros;
        sorted_array_length = (largest + 1) - smallest - zeros;
        int *sorted_array = new int[sorted_array_length - 1];
        sorted_array[0] = smallest;
        if (smallest == 0) i = 1;
        for (n = smallest; n < largest + 1; ++n) {
            if (array[n] != 0) {
                sorted_array[i] = array[n];
                i = i + 1;
            }
        }
        printf("Time taken: %.2fs\n", (double)(clock() - tStart)/CLOCKS_PER_SEC);
        delete[] array;
        array = nullptr;
        delete[] random_array;
        random_array = nullptr;
        pause();
        /* for (n = 0; n < sorted_array_length; ++n) {  // Enable only for small numbers!
            cout << n << " - " << sorted_array[n] << endl;
        } */
        delete[] sorted_array;
        sorted_array = nullptr;
    }
    return 0;
}

Fastest sorting algorithm explanation

At the beginning it randomizes the Random numbers generator and checks if the system supports Int(32) numbers. Because Int 32 Maximal Value is 2147483647 we have wide range of numbers. The program then asks you to enter a maximum number to be an upper bound on the number of all numbers in the array to sort.

The program then creates two arrays of the length entered. The first array “array” is working. The second array “random_array” fills it with random numbers. At the same time, it assigns the values of the arbitrary with the working array.

The next step is to determine the smallest and largest elements in the random number array.

The elements with value zero in the working array are counted, with bounds smallest element – largest element. If the smallest element is zero, the number of zeros is decremented by one.
A pointer to a new array “sorted_array” is created. Index zero is assigned the value of the smallest element.

A loop is started for the working array for which each element is checked. If the element is non-zero it is assigned to the current index of the “sorted_array”.

The result is printed, taking into account the execution time.

Clearing memory from arrays and pointers.

Demonstration for fastest sorting algorithm.

Learn more about sorting algorithms.