Algorithm for fastest sorting of positive integers. An example of the C++ language of the fastest sorting algorithm.

Years ago, I had the idea to create perhaps the fastest sorting algorithm for positive 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.

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.

Enter the upper limit on the number of all numbers in the array to sort.

The program creates two arrays of the length entered. The first array “array” is working value. 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 program print the result, taking into account the execution time.

Clearing memory from arrays and pointers.

Run code demonstration for fastest sorting algorithm.