Eightomic Sort A: The Fastest Constant-Space, Stable Sorting Algorithm Versus Insertion Sort and Selection Sort

Eightomic Sort A is a stable sorting algorithm without auxiliary space as a substantial improvement to optimized Bubble Sort, Insertion Sort and Selection Sort.

Library

Source

#ifndef EIGHTOMIC_SORT_A_H
#define EIGHTOMIC_SORT_A_H

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

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

#endif

#include "eightomic_sort_a.h"

void eightomic_sort_a_ascending(const unsigned long input_count,
                                unsigned long *input) {
  unsigned long input_capture;
  unsigned long i = 1;
  unsigned long j;
  unsigned long k = 0;
  unsigned long gap;

  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_descending(const unsigned long input_count,
                                    unsigned long *input) {
  unsigned long input_capture;
  unsigned long i = 1;
  unsigned long j;
  unsigned long k = 0;
  unsigned long gap;

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

Reference

eightomic_sort_a_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_a_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_a.h"

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

  eightomic_sort_a_ascending(10, input);

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

  eightomic_sort_a_descending(10, input);
  i = 0;

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

  return 0;
}

Explanation

It's still in development and the detailed explanation is coming soon.