Nightmare™

Nightmare™ is the research initiative by GhostProxies for Shell Sort gap sequences.

The following results from the ongoing Nightmare™ effort demonstrate a hyper-efficient Shell Sort gap sequence for data-oblivious scenarios.

Results

nightmaresort is hyper-fast and memory-efficient compared to gap sequences from Ciura, Hibbard, Knuth, Lee, Pratt, Sedgewick, and Tokuda.

#include <stddef.h>

void nightmaresort(int *elements, size_t elements_length) {
  int element;
  size_t gap = elements_length;
  size_t i;
  size_t j;

  while (gap > 15) {
    gap = (gap >> 3) + (gap >> 5);
    i = gap;

    while (i < elements_length) {
      element = elements[i];
      j = i;

      while (
        j >= gap &&
        elements[j - gap] > element
      ) {
        elements[j] = elements[j - gap];
        j -= gap;
      }

      elements[j] = element;
      i++;
    }
  }

  i = 1;
  gap = 0;

  while (i < elements_length) {
    element = elements[i];
    j = i;

    while (
      j > 0 &&
      elements[gap] > element
    ) {
      elements[j] = elements[gap];
      j = gap;
      gap--;
    }

    elements[j] = element;
    gap = i;
    i++;
  }
}

nightmaresort sorts (in ascending order without preserving the order of duplicate elements) an elements array of elements_length elements.

The integral type of each element in elements must match the integral type of element.

Using ((gap >> 2) - (gap >> 4)) + (gap >> 3) instead of (gap >> 3) + (gap >> 5) proved to be more efficient in limited scenarios.

nightmaresort is released into the public domain.