I'm not well versed in that area. Looks like the compiler is doing something differently when you free up a registry space, but it's still slower.

int tailing_binary_search(int *array, int array_size, int key)
{
register int bot, mid, i;

    if (key < array\[0\])
    {
            return -1;
    }

    bot = 0;
    i = array\_size - 1;
    mid = i / 2;

    while (bot + 7 < i)
    {
            if (key < array\[mid\])
            {
                    i = mid - 1;
                    mid -= (i - bot) / 2;
            }
            else
            {
                    bot = mid;
                    mid += (i - bot) / 2;
            }
    }
    while (key < array\[i\]) --i;

    if (key == array\[i\])
    {
            return i;
    }
    return -1;

}

Using a midpoint and a span is slower because it requires 2 assignments per loop opposed to 1.5 (on average) in my implementation. I assume it's the fixup and assignment issue that left academics stumped for the past 60 years. There are also caching issues for larger arrays, for which I've created a variant that is mindful in that regard.

It switches to a linear search when roughly 8 elements are left. The i != 0 check is there in case the key is smaller than the value at index 0.

I've been playing around with binary search algorithms and have created a novel new variant that appears to be significantly faster than any traditional implementations I've seen.

int boundless_binary_search(int *array, int array_size, int key)
{
register int mid, i;

    mid = i = array\_size - 1;

    while (mid > 7)
    {
            mid = mid / 2;

            if (key < array\[i - mid\]) i -= mid;
    }
    while (i && key < array\[i\]) --i;

    if (key == array\[i\])
    {
            return i;
    }
    return -1;

}

I'm wondering if this is a novel binary search implementation, or has this approach been used by someone before? Some variants and benchmark graphs: https://sites.google.com/site/binarysearchcube/binary-search[^]

libdivsufsort implements a suffix array, which according to some sources is about as fast as quicksort. I made some improvements to the memory handling of Cubesort and it now is 1.21 times slower than mergesort for random data, and 5.75 times faster for sorted data. Might see further improvement gains by setting BSC_L to 1 when comparing strings.

In my own tests cubesort is 2 times slower than mergesort for random integers and 2.5 times faster for sorted integers. This is using the latest version which I uploaded today and improves performance by about 25%. I'm not sure if this gap can be closed as mergesort has superior cache performance for random data. I haven't been able to find a decent quicksort implementation. Cubesort seems best suited for cases where a data set is for more than 50% in order. When I have a couple of hours I'll make a string based version of cubesort (very easy) and see how fast it sorts the file. Does the file contain duplicates? Edit: It appears the file is in reverse order. Takes about 3.5 seconds to load the file, 5 seconds to sort it using cubesort.

I've created a new sorting algorithm which allows O(1) sorting of ordered data, O(log (root n)) sorting of partially sorted data, and O(log n) sorting of random data. The underlying mechanism is well suited for a general purpose data structure, which I'm calling a binary search cube, and has notable advantages over binary trees. The data structure is cube-shaped rather than tree-shaped. I've described the data structure and sorting algorithm on the following webpage: https://sites.google.com/site/binarysearchcube/ The site also includes three programs written in C, one of them implementing cubesort using a 4 dimensional search cube, and an implementation of a 3 and 4 dimensional binary search cube. Haven't been able to properly benchmark the software against other sorting algorithms and data structures, but the memory overhead is significantly less. Hoping for some interesting feedback.