Eightomic Sort B: The Fastest Constant-Space Sorting Algorithm Versus All Shell Sort Gap Sequences and Heap Sort

Eightomic Sort B is a bitwise calculation for an optimal sequence of unstable Shell Sort gaps as a substantial improvement to Ciura, Knuth, Sedgewick and Tokuda sequences.

Library

Source

#ifndef EIGHTOMIC_SORT_B_H
#define EIGHTOMIC_SORT_B_H

void eightomic_sort_b_ascending(const unsigned long input_count,
                                unsigned long *input);

void eightomic_sort_b_descending(const unsigned long input_count,
                                 unsigned long *input);

#endif

#include "eightomic_sort_b.h"

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++;
  }
}

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.

Example

#include <stdio.h>
#include "eightomic_sort_b.h"

int main(void) {
  unsigned long input[10] = {1, 111, 111, 11, 111111, 111, 1, 11, 111111111, 1};
  unsigned long i = 0;

  eightomic_sort_b_ascending(10, input);

  while (i < 10) {
    printf("%u\n", input[i]);
    i++;
  }

  eightomic_sort_b_descending(10, input);
  i = 0;

  while (i < 10) {
    printf("%u\n", input[i]);
    i++;
  }

  return 0;
}

Explanation

Eightomic Sort B 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 gapped_cocktail_shaker_sort_ascending(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 in Eightomic Sort B 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    3

After sorting with each gap value, it falls through to an optimized 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 both Eightomic PRNG 16 B and Eightomic PRNG 32 A to randomize unsorted data.

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.