Eightomic
CoherenceSort B
It's the fastest constant-space sorting algorithm versus Shell Sort gap sequences and Heap Sort.
Algorithm
Source
void eightomic_sort_b_ascending(const unsigned long input_count,
unsigned long *input) {
unsigned long input_capture;
unsigned long gap = input_count;
unsigned long i;
unsigned long j;
while (gap > 15) {
gap = (gap >> 5) + (gap >> 3);
i = gap;
while (i < input_count) {
input_capture = input[i];
j = i;
while (
j >= gap &&
input[j - gap] > input_capture
) {
input[j] = input[j - gap];
j -= gap;
}
input[j] = input_capture;
i++;
}
}
i = 1;
gap = 0;
while (i < input_count) {
input_capture = input[i];
j = i;
while (
j > 0 &&
input[gap] > input_capture
) {
input[j] = input[gap];
j = gap;
gap--;
}
input[j] = input_capture;
gap = i;
i++;
}
}
void eightomic_sort_b_descending(const unsigned long input_count,
unsigned long *input) {
unsigned long input_capture;
unsigned long gap = input_count;
unsigned long i;
unsigned long j;
while (gap > 15) {
gap = (gap >> 5) + (gap >> 3);
i = gap;
while (i < input_count) {
input_capture = input[i];
j = i;
while (
j >= gap &&
input[j - gap] < input_capture
) {
input[j] = input[j - gap];
j -= gap;
}
input[j] = input_capture;
i++;
}
}
i = 1;
gap = 0;
while (i < input_count) {
input_capture = input[i];
j = i;
while (
j > 0 &&
input[gap] < input_capture
) {
input[j] = input[gap];
j = gap;
gap--;
}
input[j] = input_capture;
gap = i;
i++;
}
}
License
It's free and open source.
Reference
eightomic_sort_b_ascending() is the sorting function in ascending order that accepts the following 2 arguments in left-to-right order.
1: input_count is the const unsigned long count of elements in the input array.
2: input is the unsigned long array to sort. The data type is interchangeable with any integral data type and must match the integral data type of input_capture.
The return value data type is void.
eightomic_sort_b_descending() is the sorting function in descending order that accepts the following 2 arguments in left-to-right order.
1: input_count is the const unsigned long count of elements in the input array.
2: input is the unsigned long array to sort. The data type is interchangeable with any integral data type and must match the integral data type of input_capture.
The return value data type is void.
Explanation
It doesn't pre-calculate the upper limit with a loop starting from 0.
Instead, the gap numbers in each sorting instance are dynamically-calculated with inconsistencies among different input_count values.
The gap sequence calculation formula structure (input_count >> a) + (input_count >> b) is a derivative of the following failed attempt from Eightomic to optimize Cocktail Shaker Sort with unstable gap increments.
void unstable_cocktail_shaker_sort(unsigned long input_count,
unsigned long *input) {
unsigned long input_capture;
unsigned long gap;
unsigned long i;
unsigned long j;
unsigned char is_sorted;
if (input_count > 1) {
i = 0;
j = (input_count >> 12) + (input_count >> 7) + 1;
is_sorted = 0;
while (is_sorted == 0) {
gap = (input_count >> 15) + (input_count >> 14) + 1;
is_sorted = 1;
while (i < j) {
while (j < input_count) {
if (input[i] > input[j]) {
input_capture = input[i];
input[i] = input[j];
input[j] = input_capture;
}
i++;
j++;
}
if (((input_count - i) >> 12) > 0) {
gap++;
}
i += gap;
if (i >= j) {
i = j - 1;
}
while (i > 0) {
i--;
j--;
if (input[i] > input[j]) {
input_capture = input[i];
input[i] = input[j];
input[j] = input_capture;
is_sorted = 0;
}
}
j--;
}
if (is_sorted == 0) {
i = 0;
if (input_count > 128) {
j = (input_count >> 15) + (input_count >> 14) + 8;
} else {
j = 1;
}
}
}
}
}Although the aforementioned failure isn't as fast as unoptimized Shell Sort, the bitwise gap calculation is fastest when a is 12 and b is 7.
Eightomic Sort B uses the same formula structure and a similar right-shift operand ratio with a as 5 and b as 3.
Elements are always guaranteed to be sorted within bounds using conditional statements that guarantee the final pass is always a regular Insertion Sort with a gap value of 1.
After each pass, gap > 15 prevents any result of gap calculation from using a value of 0 or 1 based on the following calculation output table.
Gap Calculation
Result
0 0
1 0
2 0
3 0
4 0
5 0
6 0
7 0
8 1
9 1
10 1
11 1
12 1
13 1
14 1
15 1
16 3
17 3
18 3It doesn't pre-calculate a consistent gap sequence that has an upper limit.
Instead, each sorting instance calculates a gap sequence dynamically with inconsistencies among different input_count values as a derivative of a failed attempt to optimize Cocktail Shaker Sort.
After sorting with each gap value, it falls through to the fastest optimization of Insertion Sort.
Compared to every Shell Sort gap sequence, it's faster across all data types, randomized distributions and sizes of input elements.
It's the fastest in-place sorting algorithm on average among all sorting algorithms that don't allocate additional memory for input partitions, including Heap Sort.
The speed's close to Insertion Sort for small input sizes, then it scales to the fastest Shell Sort gap sequence for all input data types and unsorted distributions.
It's tested using Entropy PRNGs to randomize unsorted data across a wide range of distributions.
Furthermore, it's faster for mostly-sorted and sorted arrays.
The aforementioned speed comparisons are relative to optimized Ciura, Hibbard, Knuth, Papernov & Stasevich, Pratt, Sedgewick and Tokuda gap sequences.
