Sort A

Sort A Stable

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

Algorithm

Source

#include <stdint.h>

void eightomic_sort_a_stable_ascending(const uintptr_t input_count,
                                       int *input) {
  int input_capture;
  uintptr_t gap;
  uintptr_t i = 1;
  uintptr_t j;
  uintptr_t k = 0;

  if (input_count < 200) {
    while (i < input_count) {
      input_capture = input[i];
      j = i;

      while (
        j > 0 &&
        input[k] > input_capture
      ) {
        input[j] = input[k];
        j = k;
        k--;
      }

      input[j] = input_capture;
      k = i;
      i++;
    }

    return;
  }

  while (i < input_count) {
    if (input[i - 1] <= input[i]) {
      i++;
      continue;
    }

    input_capture = input[i];
    j = i;

    if (input[0] <= input_capture) {
      k = i;

      while (input[k - 1] > input_capture) {
        k >>= 1;
      }

      if (j > k) {
        gap = (k >> 3) + (k >> 2) + 1;
        k <<= 1;

        while (input[k - gap] > input_capture) {
          k -= gap;
          gap = (k >> 1) + 1;
        }

        while (gap > (input_count >> 6)) {
          gap >>= 1;

          while (input[k - gap] > input_capture) {
            k -= gap;
            gap = (k >> 1) + 1;
          }
        }

        while (input[k - 1] > input_capture) {
          k--;
        }

        while (j > k) {
          input[j] = input[j - 1];
          j--;
        }

        input[j] = input_capture;
      }

      i++;
      continue;
    }

    while (j > 0) {
      input[j] = input[j - 1];
      j--;
    }

    input[j] = input_capture;
    i++;
  }
}

void eightomic_sort_a_stable_descending(const uintptr_t input_count,
                                        int *input) {
  int input_capture;
  uintptr_t gap;
  uintptr_t i = 1;
  uintptr_t j;
  uintptr_t k = 0;

  if (input_count < 200) {
    while (i < input_count) {
      input_capture = input[i];
      j = i;

      while (
        j > 0 &&
        input[k] < input_capture
      ) {
        input[j] = input[k];
        j = k;
        k--;
      }

      input[j] = input_capture;
      k = i;
      i++;
    }

    return;
  }

  while (i < input_count) {
    if (input[i - 1] >= input[i]) {
      i++;
      continue;
    }

    input_capture = input[i];
    j = i;

    if (input[0] >= input_capture) {
      k = i;

      while (input[k - 1] < input_capture) {
        k >>= 1;
      }

      if (j > k) {
        gap = (k >> 3) + (k >> 2) + 1;
        k <<= 1;

        while (input[k - gap] < input_capture) {
          k -= gap;
          gap = (k >> 1) + 1;
        }

        while (gap > (input_count >> 6)) {
          gap >>= 1;

          while (input[k - gap] < input_capture) {
            k -= gap;
            gap = (k >> 1) + 1;
          }
        }

        while (input[k - 1] < input_capture) {
          k--;
        }

        while (j > k) {
          input[j] = input[j - 1];
          j--;
        }

        input[j] = input_capture;
      }

      i++;
      continue;
    }

    while (j > 0) {
      input[j] = input[j - 1];
      j--;
    }

    input[j] = input_capture;
    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_stable_ascending() and eightomic_sort_a_stable_descending() must not change.

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

Reference

eightomic_sort_a_stable_ascending() and eightomic_sort_a_stable_descending() are the stable 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_stable_ascending() sorts numbers in ascending order while preserving original sort order context.

eightomic_sort_a_stable_descending() sorts numbers in descending order while preserving original sort order context.

Classification

It's in the same class as Bubble Sort, Insertion Sort and Stable Binary Insertion Sort.

Speed

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

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.

input_count < 200 ensures all sorting instances with less than 200 elements use a fast optimization of Insertion Sort to compensate for the conditional statement.

Other sorting instances fall through to a stable, unique Binary Insertion Sort derivative with one-way searching at specific offset calculations based on both the high bounds of sorted data and input_count.

200 was selected as the lowest input_count that’s faster than unoptimized Insertion Sort on average in speed tests by Eightomic.

if (input[i - 1] <= input[i]) skips through sorted runs quickly for larger input sizes, making it faster for mostly-sorted and sorted arrays.

The unsorted element to insert in its sorted place is stored in input_capture.

if (input[0] <= input_capture) verifies that the element to insert isn’t less than or equal to the first array element, otherwise it falls through to an Insertion Sort operation with less comparisons as it swaps all elements until reaching 0.

When the first element is the smallest element compared to input_capture, the high bound k is decreased by half until reaching a point where input_capture is less than the element at index k.

while (input[k - 1] > input_capture) ensures that each adjacent, sorted element is never skipped before halving the index k with k >>= 1.

When k overshoots the insertion point, it calculates a gap starting point at an offset that’s near 37.5% of the decreased, overshot high bound k by using gap = (k >> 3) + (k >> 2) + 1, then it doubles k to reset it back to a position where input_capture is less than or equal to the element at the high bound k.

The doubling of k is always safely within the bounds of input_count because the conditional statement if (j > k) verifies that k was already halved at least once.

Then, it performs a one-way Binary Search that decreases k by gap and decreases gap by (gap >> 1) + 1.

gap is always much smaller than k, so k -= gap always decreases safely within bounds.

while (input[k - gap] > input_capture) always breaks out of the loop because input[0] is already validated as less than or equal to input_capture.

The following demonstration proves the aforementioned safety by testing each possible input_count value up to 1 billion.

#include <stdint.h>
#include <stdio.h>

int main(void) {
  uintptr_t i = 100;
  uintptr_t j;
  uintptr_t gap;
  uintptr_t out_of_bounds_error_count = 0;

  while (i < 1000000000) {
    j = i >> 1;
    gap = (j >> 3) + (j >> 2) + 1;
    j <<= 1;

    while (
      gap > 1 &&
      (j - gap) > 0
    ) {
      j -= gap;
      gap = (j >> 1) + 1;
    }

    if (j == 0) {
      out_of_bounds_error_count++;
    }

    i++;
  }

  if (out_of_bounds_error_count == 0) {
    printf("There are no out-of-bounds indices.\n");
  }
}

The next loop while (gap > (input_count >> 6)) repeats the one-way Binary Search at a large-enough gap size relative to input_count.

input_count >> 6 was chosen as a stopping bound because it yielded faster speeds on average than other shift values.

Then, while (input[k — 1] > input_capture) corrects the stability of the k index by decrementing k-- until the correct insertion position is found.