I have recently implemented a sorting algorithm in c and decide to time it against quicksort (see here for the timing method). As I expected, it was slower by multitudes, but when I lowered the difference between the minimum and maximum values in the array the times for my homebrew sorting algorithm became progressively smaller. I eventually made the difference between the minimum and maximum values to 5 and it became lightning fast. On 3 runs with an array with 100 000 elements, I got speeds of 0.0391 milliseconds, 0.0504 milliseconds, and 0.0372 milliseconds!
Here is the code I used:
#include<string.h>
void sort(int* unsorted, const int size) {
int sorted_index[size];
int sorted[size];
int unsorted_copy[size];
memcpy(unsorted_copy, unsorted, sizeof unsorted_copy);
int unsorted_min = unsorted[0];
for (int i = 0; i < size; i++) {
if (unsorted[i] < unsorted_min) {
unsorted_min = unsorted[i];
}
}
int sorted_length = 0;
int i = 0;
while (sorted_length < size) {
for (; i < size; i++) {
if (unsorted[i] == NULL) {
continue;
}
if (unsorted[i] == unsorted_min) {
sorted_index[sorted_length] = i;
unsorted[i] = NULL;
sorted_length++;
}
else {
unsorted[i]--;
}
}
i = 0;
}
for (int j = 0; j < size; j++) {
sorted[j] = unsorted_copy[sorted_index[j]];
}
memcpy(unsorted, sorted, sizeof sorted);
}
As you can see, the program recursively diminishes the values in the array, until they reach the minimum value in the array. At that point, it inserts the index of the value into a new array. At the end of the loops, it inserts the value of unsorted copy[sorted index] into the original array.
Is this technique already a thing or have I invented this.
Thanks in advance!