Sort A

Sort A Unstable

It's a fast, in-place, non-auxiliary sorting algorithm that discards original sort order context.

Algorithm

Source

#include <stdint.h>

void eightomic_sort_a_unstable_ascending(const uintptr_t input_count,
                                         int *input) {
  int input_capture;
  uintptr_t gap = input_count;
  uintptr_t long i;
  uintptr_t 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_a_unstable_descending(const uintptr_t input_count,
                                          int *input) {
  int input_capture;
  uintptr_t gap = input_count;
  uintptr_t i;
  uintptr_t 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 requires a purchase of $80 for a proprietary license that permits usage subject to the following condition.

The function names eightomic_sort_a_unstable_ascending() and eightomic_sort_a_unstable_descending() must not change.

The aforementioned source is viewable publicly to permit a limited evaluation period.

Reference

eightomic_sort_a_unstable_ascending() and eightomic_sort_a_unstable_descending() are the unstable sorting functions that accept the following 2 arguments in left-to-right order.

1: input_count is the const uintptr_t count of elements in the input array.

2: input is the int 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_a_unstable_ascending() sorts numbers in ascending order while discarding original sort order context.

eightomic_sort_a_unstable_descending() sorts numbers in descending order while discarding original sort order context.

Classification

It's in the same class as Heap Sort, Selection Sort, Shell Sort and Unstable Binary Insertion Sort.

Speed

It's possibly the fastest unstable sorting algorithm that doesn't require substantial auxiliary space for sorted runs or unsorted subarrays.

It'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.

Eightomic hasn’t found any sorting instances across a wide range of distributions that are slower by comparison, but the possibility may exist.

Security

The following security explanation uses the context of ascending sort order.

The gap sequence calculation formula structure (input_count >> a) + (input_count >> b) is a derivative of a failed attempt by Eightomic to optimize Cocktail Shaker Sort.

The consistent decrements from gap = (gap >> 5) + (gap >> 3) ensure there are never pitfalls that cause critically-slow sorting instances with any combination of numbers.

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   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

It 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.

After sorting with each gap value greater than 1, it falls through to a hard-coded, optimized variation of Insertion Sort.