Coherence

Sort data efficiently with optimal, unique stable and unstable sorting algorithms.

Library

Eightomic Sort A

The fastest constant-space, stable sorting algorithm versus Insertion Sort and Selection Sort.

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

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.

It's still being tested with all sorting instances and the full description is in progress.

Eightomic Sort B

The fastest constant-space sorting algorithm versus all Shell Sort gap sequences and Heap Sort.

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

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.

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

Eightomic Sort C

The fastest linear-space, stable sorting algorithm that replaces Merge Sort, Radix Sort and Tim Sort.

It's not available yet.

Eightomic Sort D

The fastest linear-space sorting algorithm versus Quick Sort.

It's not available yet.

License

Eightomic License

© Eightomic <https://eightomic.com>

Permission to both copy this software and use copies of this software is
granted only when the following 2 conditions are satisfied.

1. These software license conditions in entirety, both unmodified and without
   obfuscation, must be included wherever an instance of either a copy of this
   software or a derivation from a copy of this software is implemented.

2. Liability for damages incurred in conjunction with this software must not
   be assumed by Eightomic.