Timsort — the fastest sorting algorithm you’ve never heard of

[Protools5LEGuy]

Timsort: A very fast , O(n log n), stable sorting algorithm built for the real world — not constructed in academia.

Timsort is a sorting algorithm that is efficient for real-world data and not created in an academic laboratory. Tim Peters created Timsort for the Python programming language in 2001. Timsort first analyses the list it is trying to sort and then chooses an approach based on the analysis of the list.

https://skerritt.blog/timsort-the-fastest-sorting-algorithm-youve-never-heard-of/

[OS923]

The idea of using runs is good, but then you merge lists of different length, which is not optimal. Insertion sort for lists of 64 elements is bad.

I'll measure it when I have time.

[OS923]

He claims that in the worst case it's still as fast as MergeSort. I don't think so. If all elements are in reverse order, then searching for runs is a waste of time and he still has to do the MergeSort.

He proposes other 'improvements' too, like if the first element of the first list sorts after the last element of the second list then he just concatenates the lists. He seems to forget how many comparisons this requires.

[OS923]

It sees descending runs and reverses them.

[OS923]

I wrote TimSort for OS 9. It's based on Google's code from 2009. For perfectly randomized sequences it's 41% slower than MergeSort. For ordered or almost ordered sequences it's up to 20 times faster than MergeSort.

There's a strange instruction:

Code: [Select]

while ((count1 | count2)<minGallop);What's the logic of that? It looks like an error.

I changed it into

Code: [Select]

while ((count1<minGallop) or (count2<minGallop));This is 1.4% slower.

Then I changed it into

Code: [Select]

while ((count1<minGallop) and (count2<minGallop));This is 1.9% slower.

What should I do?

[OS923]

According to the description of the algorithm it has to be

Code: [Select]

while ((count1 + count2)<minGallop);
This looks like a rather arbitrary decision and it doesn't make much difference.

[OS923]

I tried this again:

Code: [Select]

while (count1+count2<minGallop);and it was 2.3% faster, but there's a small chance that it's not sorted correctly.

I sorted 1000 sequences of 2^20 random numbers with

Code: [Select]

while ((count1|count2)<minGallop);and it was correct. Don't ask me why because I don't understand it.

[OS923]

I forgot a

Code: [Select]

if (breakOuter)
    {
    break;
    }or two.

This version works correctly with (count1 + count2):

Code: [Select]

#pragma once

class TimSort
{
private:
    // Private types.
    struct Array
        {
        SInt32 count;
        SInt32 *elements;
        };

    // Global data.
    static const SInt32 INITIAL_TMP_STORAGE_LENGTH=256;
    static const SInt32 MIN_GALLOP=7;
    static const SInt32 MIN_MERGE=32;
    static SInt32 s_minGallop;
    static SInt32 s_stackSize;
    static SInt32 *s_runBase;
    static SInt32 *s_runLen;
    static Array s_tmp;

    // Globale functions.
public:
    static void Sort(SInt32 count,
                     SInt32 *elements);
private:
    static void Sort(Array &a);
    static void BinarySort(Array &a,
                           SInt32 lo,
                           SInt32 hi,
                           SInt32 start);
    static SInt32 CountRunAndMakeAscending(Array &a,
                                           SInt32 lo,
                                           SInt32 hi);
    static void ReverseRange(Array &a,
                             SInt32 lo,
                             SInt32 hi);
    static SInt32 MinRunLength(SInt32 n);
    static void PushRun(SInt32 runBase,
                        SInt32 runLen);
    static void MergeCollapse(Array &a);
    static void MergeForceCollapse(Array &a);
    static void MergeAt(Array &a,
                        SInt32 i);
    static SInt32 GallopLeft(SInt32 key,
                             Array &a,
                             SInt32 base,
                             SInt32 len,
                             SInt32 hint);
    static SInt32 GallopRight(SInt32 key,
                              Array &a,
                              SInt32 base,
                              SInt32 len,
                              SInt32 hint);
    static void MergeLo(Array &a,
                        SInt32 base1,
                        SInt32 len1,
                        SInt32 base2,
                        SInt32 len2);
    static void MergeHi(Array &a,
                        SInt32 base1,
                        SInt32 len1,
                        SInt32 base2,
                        SInt32 len2);
    static void EnsureCapacity(SInt32 a_count,
                               SInt32 minCapacity);
    static SInt32 Min(SInt32 x,
                      SInt32 y);
    static SInt32 Compare(SInt32 x,
                          SInt32 y);
    static void ArrayCopy(SInt32 *source,
                          SInt32 sourceIndex,
                          SInt32 *destination,
                          SInt32 destinationIndex,
                          SInt32 length);

    // Forbidden.
    TimSort();
};

Code: [Select]

#include "TimSort.h"

#define X() ((count1+count2)<minGallop)
#define Y() ((count1>=minGallop) or (count2>=minGallop))

SInt32 TimSort::s_minGallop=MIN_GALLOP;

SInt32 TimSort::s_stackSize=0;

SInt32 *TimSort::s_runBase=nil;

SInt32 *TimSort::s_runLen=nil;

TimSort::Array TimSort::s_tmp;

void TimSort::Sort(const SInt32 count,
                   SInt32* const elements)
{
    s_tmp.count=(count<(INITIAL_TMP_STORAGE_LENGTH<<1)) ? count>>1 : INITIAL_TMP_STORAGE_LENGTH;
    s_tmp.elements=new SInt32[s_tmp.count];
    if (!s_tmp.elements)
        {
        exit(0);
        }

    const SInt32 stackLen=(count<120) ? 5 : (count<1542 ? 10 : (count<119151 ? 19 : 40));

    s_runBase=new SInt32[stackLen];
    if (!s_runBase)
        {
        exit(0);
        }

    s_runLen=new SInt32[stackLen];
    if (!s_runLen)
        {
        exit(0);
        }

    Array a;
    a.count=count;
    a.elements=elements;
    Sort(a);

    s_stackSize=0;

    delete [] s_runBase;
    s_runBase=nil;

    delete [] s_runLen;
    s_runLen=nil;

    delete [] s_tmp.elements;
    s_tmp.elements=nil;

    s_tmp.count=0;
}

void TimSort::Sort(Array &a)
{
    SInt32 lo=0;
    const SInt32 hi=a.count;

    SInt32 nRemaining=hi-lo;
    if (nRemaining<2)
        {
        return;
        }
    if (nRemaining<MIN_MERGE)
        {
        const SInt32 initRunLen=CountRunAndMakeAscending(a,
                                                         lo,
                                                         hi);
        BinarySort(a,
                   lo,
                   hi,
                   lo+initRunLen);
        return;
        }

    const SInt32 minRun=MinRunLength(nRemaining);
    do
        {
        SInt32 runLen=CountRunAndMakeAscending(a,
                                               lo,
                                               hi);


        if (runLen<minRun)
            {
            const SInt32 force=(nRemaining<=minRun) ? nRemaining : minRun;
            BinarySort(a,
                       lo,
                       lo+force,
                       lo+runLen);
            runLen=force;
            }
        PushRun(lo,
                runLen);
        MergeCollapse(a);
        lo+=runLen;
        nRemaining-=runLen;
        }
    while (nRemaining);
    MergeForceCollapse(a);
}

void TimSort::BinarySort(Array &a,
                         const SInt32 lo,
                         const SInt32 hi,
                         SInt32 start)
{
    if (start==lo)
        {
        start++;
        }
    while (start<hi)
        {
        const SInt32 pivot=a.elements[start];
        SInt32 left=lo;
        SInt32 right=start;
        while (left<right)
            {
            const SInt32 mid=(left+right)>>1;
            const SInt32 c=Compare(pivot,
                                   a.elements[mid]);
            if (c<0)
                {
                right=mid;
                }
            else
                {
                left=mid+1;
                }
            }
        const SInt32 n=start-left;
        switch (n)
            {
            case 2:
                {
                a.elements[left+2]=a.elements[left+1];
                }
            case 1:
                {
                a.elements[left+1]=a.elements[left];
                break;
                }
            default:
                {
                ArrayCopy(a.elements,
                          left,
                          a.elements,
                          left+1,
                          n);
                }
            }
        a.elements[left]=pivot;
        start++;
        }
}

SInt32 TimSort::CountRunAndMakeAscending(Array &a,
                                         const SInt32 lo,
                                         const SInt32 hi)
{
    SInt32 runHi=lo+1;
    if (runHi==hi)
        {
        return 1;
        }

    SInt32 c=Compare(a.elements[runHi++],
                     a.elements[lo]);
    if (c<0)
        {
        while (runHi<hi)
            {
            c=Compare(a.elements[runHi],
                      a.elements[runHi-1]);
            if (c<0)
                {
                runHi++;
                }
            else
                {
                break;
                }
            }
        ReverseRange(a,
                     lo,
                     runHi);
        }
    else
        {
        while (runHi<hi)
            {
            c=Compare(a.elements[runHi],
                      a.elements[runHi-1]);
            if (c>=0)
                {
                runHi++;
                }
            else
                {
                break;
                }
            }
        }

    return runHi-lo;
}

void TimSort::ReverseRange(Array &a,
                           SInt32 lo,
                           SInt32 hi)
{
    hi--;
    while (lo<hi)
        {
        const SInt32 t=a.elements[lo];
        a.elements[lo++]=a.elements[hi];
        a.elements[hi--]=t;
        }
}

SInt32 TimSort::MinRunLength(SInt32 n)
{
    SInt32 r=0;
    while (n>=MIN_MERGE)
        {
        r or_eq (n bitand 1);
        n>>=1;
        }
    return n+r;
}

void TimSort::PushRun(const SInt32 runBase,
                      const SInt32 runLen)
{
    s_runBase[s_stackSize]=runBase;
    s_runLen[s_stackSize]=runLen;
    s_stackSize++;
}

void TimSort::MergeCollapse(Array &a)
{
    while (s_stackSize>1)
        {
        SInt32 n=s_stackSize-2;
        if ((n>0) and (s_runLen[n-1]<=s_runLen[n]+s_runLen[n+1]))
            {
            if (s_runLen[n-1]<s_runLen[n+1])
                {
                n--;
                }
            MergeAt(a,
                    n);
            }
        else if (s_runLen[n]<=s_runLen[n+1])
            {
            MergeAt(a,
                    n);
            }
        else
            {
            break;
            }
        }
}

void TimSort::MergeForceCollapse(Array &a)
{
    while (s_stackSize>1)
        {
        SInt32 n=s_stackSize-2;
        if ((n>0) and (s_runLen[n-1]<s_runLen[n+1]))
            {
            n--;
            }
        MergeAt(a,
                n);
        }
}

void TimSort::MergeAt(Array &a,
                      const SInt32 i)
{
    SInt32 base1=s_runBase[i];
    SInt32 len1=s_runLen[i];
    const SInt32 base2=s_runBase[i+1];
    SInt32 len2=s_runLen[i+1];

    s_runLen[i]=len1+len2;
    if (i==s_stackSize-3)
        {
        s_runBase[i+1]=s_runBase[i+2];
        s_runLen[i+1]=s_runLen[i+2];
        }
    s_stackSize--;

    SInt32 k=GallopRight(a.elements[base2],
                         a,
                         base1,
                         len1,
                         0);
    base1+=k;
    len1-=k;
    if (!len1)
        {
        return;
        }

    len2=GallopLeft(a.elements[base1+len1-1],
                    a,
                    base2,
                    len2,
                    len2-1);
    if (!len2)
        {
        return;
        }

    if (len1<=len2)
        {
        MergeLo(a,
                base1,
                len1,
                base2,
                len2);
        }
    else
        {
        MergeHi(a,
                base1,
                len1,
                base2,
                len2);
        }
}

SInt32 TimSort::GallopLeft(const SInt32 key,
                           Array &a,
                           const SInt32 base,
                           const SInt32 len,
                           const SInt32 hint)
{
    SInt32 lastOfs=0;
    SInt32 ofs=1;

    SInt32 c=Compare(key,
                     a.elements[base+hint]);
    if (c>0)
        {
        const SInt32 maxOfs=len-hint;
        while (ofs<maxOfs)
            {
            c=Compare(key,
                      a.elements[base+hint+ofs]);
            if (c>0)
                {
                lastOfs=ofs;
                ofs=(ofs<<1)+1;
                if (ofs<=0)
                    {
                    ofs=maxOfs;
                    }
                }
            else
                {
                break;
                }
            }
        if (ofs>maxOfs)
            {
            ofs=maxOfs;
            }
        lastOfs+=hint;
        ofs+=hint;
        }
    else
        {
        const SInt32 maxOfs=hint+1;
        while (ofs<maxOfs)
            {
            c=Compare(key,
                      a.elements[base+hint-ofs]);
            if (c<=0)
                {
                lastOfs=ofs;
                ofs=(ofs<<1)+1;
                if (ofs<=0)
                    {
                    ofs=maxOfs;
                    }
                }
            else
                {
                break;
                }
            }
        if (ofs>maxOfs)
            {
            ofs=maxOfs;
            }
        const SInt32 tmp=lastOfs;
        lastOfs=hint-ofs;
        ofs=hint-tmp;
        }

    lastOfs++;
    while (lastOfs<ofs)
        {
        const SInt32 m=lastOfs+((ofs-lastOfs)>>1);
        c=Compare(key,
                  a.elements[base+m]);
        if (c>0)
            {
            lastOfs=m+1;
            }
        else
            {
            ofs=m;
            }
        }

    return ofs;
}

SInt32 TimSort::GallopRight(const SInt32 key,
                            Array &a,
                            const SInt32 base,
                            const SInt32 len,
                            const SInt32 hint)
{

    SInt32 ofs=1;
    SInt32 lastOfs=0;

    SInt32 c=Compare(key,
                     a.elements[base+hint]);
    if (c<0)
        {
        const SInt32 maxOfs=hint+1;
        while (ofs<maxOfs)
            {
            c=Compare(key,
                      a.elements[base+hint-ofs]);
            if (c<0)
                {
                lastOfs=ofs;
                ofs=(ofs<<1)+1;
                if (ofs<=0)
                    {
                    ofs=maxOfs;
                    }
                }
            else
                {
                break;
                }
            }
        if (ofs>maxOfs)
            {
            ofs=maxOfs;
            }
        const SInt32 tmp=lastOfs;
        lastOfs=hint-ofs;
        ofs=hint-tmp;
        }
    else
        {
        SInt32 maxOfs=len-hint;
        while (ofs<maxOfs)
            {
            c=Compare(key,
                      a.elements[base+hint+ofs]);
            if (c>=0)
                {
                lastOfs=ofs;
                ofs=(ofs<<1)+1;
                if (ofs<=0)
                    {
                    ofs=maxOfs;
                    }
                }
            else
                {
                break;
                }
            }
        if (ofs>maxOfs)
            {
            ofs=maxOfs;
            }
        lastOfs+=hint;
        ofs+=hint;
        }

    lastOfs++;
    while (lastOfs<ofs)
        {
        const SInt32 m=lastOfs+((ofs-lastOfs)>>1);
        c=Compare(key,
                  a.elements[base+m]);
        if (c<0)
            {
            ofs=m;
            }
        else
            {
            lastOfs=m+1;
            }
        }
    return ofs;
}

void TimSort::MergeLo(Array &a,
                      const SInt32 base1,
                      SInt32 len1,
                      const SInt32 base2,
                      SInt32 len2)
{
    EnsureCapacity(a.count,
                   len1);

    ArrayCopy(a.elements,
              base1,
              s_tmp.elements,
              0,
              len1);

    SInt32 cursor1=0;
    SInt32 cursor2=base2;
    SInt32 dest=base1;

    a.elements[dest++]=a.elements[cursor2++];

    if (!--len2)
        {
        ArrayCopy(s_tmp.elements,
                  cursor1,
                  a.elements,
                  dest,
                  len1);
        return;
        }

    if (len1==1)
        {
        ArrayCopy(a.elements,
                  cursor2,
                  a.elements,
                  dest,
                  len2);
        a.elements[dest+len2]=s_tmp.elements[cursor1];
        return;
        }

    SInt32 minGallop=s_minGallop;

    bool breakOuter=false;
    while (true)
        {
        SInt32 count1=0;
        SInt32 count2=0;
        do
            {
            const SInt32 c=Compare(a.elements[cursor2],
                                   s_tmp.elements[cursor1]);
            if (c<0)
                {
                a.elements[dest++]=a.elements[cursor2++];
                count2++;
                count1=0;
                if (!--len2)
                    {
                    breakOuter=true;
                    break;
                    }
                }
            else
                {
                a.elements[dest++]=s_tmp.elements[cursor1++];
                count1++;
                count2=0;
                if (--len1==1)
                    {
                    breakOuter=true;
                    break;
                    }
                }
            }
        while (X());
        if (breakOuter)
            {
            break;
            }

        do
            {
            count1=GallopRight(a.elements[cursor2],
                               s_tmp,
                               cursor1,
                               len1,
                               0);
            if (count1)
                {
                ArrayCopy(s_tmp.elements,
                          cursor1,
                          a.elements,
                          dest,
                          count1);
                dest+=count1;
                cursor1+=count1;
                len1-=count1;
                if (len1<=1)
                    {
                    breakOuter=true;
                    break;
                    }
                }
            a.elements[dest++]=a.elements[cursor2++];
            if (!--len2)
                {
                breakOuter=true;
                break;
                }

            count2=GallopLeft(s_tmp.elements[cursor1],
                              a,
                              cursor2,
                              len2,
                              0);
            if (count2)
                {
                ArrayCopy(a.elements,
                          cursor2,
                          a.elements,
                          dest,
                          count2);
                dest+=count2;
                cursor2+=count2;
                len2-=count2;
                if (!len2)
                    {
                    breakOuter=true;
                    break;
                    }
                }
            a.elements[dest++]=s_tmp.elements[cursor1++];
            if (--len1==1)
                {
                breakOuter=true;
                break;
                }
            minGallop--;
            }
        while (Y());
        if (breakOuter)
            {
            break;
            }
        if (minGallop<0)
            {
            minGallop=0;
            }
        minGallop+=2;
        }
    s_minGallop=minGallop<1 ? 1 : minGallop;

    if (len1==1)
        {
        ArrayCopy(a.elements,
                  cursor2,
                  a.elements,
                  dest,
                  len2);
        a.elements[dest+len2]=s_tmp.elements[cursor1];
        }
    else if (!len1)
        {
        exit(0);
        }
    else
        {
        ArrayCopy(s_tmp.elements,
                  cursor1,
                  a.elements,
                  dest,
                  len1);
        }
}

void TimSort::MergeHi(Array &a,
                      const SInt32 base1,
                      SInt32 len1,
                      const SInt32 base2,
                      SInt32 len2)
{
    EnsureCapacity(a.count,
                   len2);

    ArrayCopy(a.elements,
              base2,
              s_tmp.elements,
              0,
              len2);

    SInt32 cursor1=base1+len1-1;
    SInt32 cursor2=len2-1;
    SInt32 dest=base2+len2-1;

    a.elements[dest--]=a.elements[cursor1--];

    if (!--len1)
        {
        ArrayCopy(s_tmp.elements,
                  0,
                  a.elements,
                  dest-len2+1,
                  len2);
        return;
        }
    if (len2==1)
        {
        dest-=len1;
        cursor1-=len1;
        ArrayCopy(a.elements,
                  cursor1+1,
                  a.elements,
                  dest+1,
                  len1);
        a.elements[dest]=s_tmp.elements[cursor2];
        return;
        }

    SInt32 minGallop=s_minGallop;

    bool breakOuter=false;
    while (true)
        {
        SInt32 count1=0;
        SInt32 count2=0;
        do
            {
            const SInt32 c=Compare(s_tmp.elements[cursor2],
                                   a.elements[cursor1]);
            if (c<0)
                {
                a.elements[dest--]=a.elements[cursor1--];
                count1++;
                count2=0;
                if (!--len1)
                    {
                    breakOuter=true;
                    break;
                    }
                }
            else
                {
                a.elements[dest--]=s_tmp.elements[cursor2--];
                count2++;
                count1=0;
                if (--len2==1)
                    {
                    breakOuter=true;
                    break;
                    }
                }
            }
        while (X());
        if (breakOuter)
            {
            break;
            }

        do
            {
            count1=len1-GallopRight(s_tmp.elements[cursor2],
                                    a,
                                    base1,
                                    len1,
                                    len1-1);
            if (count1)
                {
                dest-=count1;
                cursor1-=count1;
                len1-=count1;
                ArrayCopy(a.elements,
                          cursor1+1,
                          a.elements,
                          dest+1,
                          count1);
                if (!len1)
                    {
                    breakOuter=true;
                    break;
                    }
                }
            a.elements[dest--]=s_tmp.elements[cursor2--];
            if (--len2==1)
                {
                breakOuter=true;
                break;
                }

            count2=len2-GallopLeft(a.elements[cursor1],
                                   s_tmp,
                                   0,
                                   len2,
                                   len2-1);
            if (count2)
                {
                dest-=count2;
                cursor2-=count2;
                len2-=count2;
                ArrayCopy(s_tmp.elements,
                          cursor2+1,
                          a.elements,
                          dest+1,
                          count2);
                if (len2<=1)
                    {
                    breakOuter=true;
                    break;
                    }
                }
            a.elements[dest--]=a.elements[cursor1--];
            if (!--len1)
                {
                breakOuter=true;
                break;
                }
            minGallop--;
            }
        while (Y());
        if (breakOuter)
            {
            break;
            }
        if (minGallop<0)
            {
            minGallop=0;
            }
        minGallop+=2;
        }
    s_minGallop=(minGallop<1) ? 1 : minGallop;

    if (len2==1)
        {
        dest-=len1;
        cursor1-=len1;
        ArrayCopy(a.elements,
                  cursor1+1,
                  a.elements,
                  dest+1,
                  len1);
        a.elements[dest]=s_tmp.elements[cursor2];
        }
    else if (!len2)
        {
        exit(0);
        }
    else
        {
        ArrayCopy(s_tmp.elements,
                  0,
                  a.elements,
                  dest-len2+1,
                  len2);
        }
}

void TimSort::EnsureCapacity(const SInt32 a_count,
                             const SInt32 minCapacity)
{
    if (s_tmp.count>=minCapacity)
        {
        return;
        }

    SInt32 newSize=minCapacity;
    newSize or_eq newSize>>1;
    newSize or_eq newSize>>2;
    newSize or_eq newSize>>4;
    newSize or_eq newSize>>8;
    newSize or_eq newSize>>16;
    newSize++;

    if (newSize<0)
        {
        newSize=minCapacity;
        }
    else
        {
        newSize=Min(newSize,
                    a_count>>1);
        }

    delete [] s_tmp.elements;

    s_tmp.elements=new SInt32[newSize];
    if (!s_tmp.elements)
        {
        exit(0);
        }
    s_tmp.count=newSize;
}

SInt32 TimSort::Min(const SInt32 x,
                    const SInt32 y)
{
    if (x<y)
        {
        return x;
        }
    return y;
}

SInt32 TimSort::Compare(const SInt32 x,
                        const SInt32 y)
{
    if (x<y)
        {
        return -1;
        }
    if (x>y)
        {
        return 1;
        }
    return 0;
}

void TimSort::ArrayCopy(SInt32* const source,
                        const SInt32 sourceIndex,
                        SInt32* const destination,
                        const SInt32 destinationIndex,
                        SInt32 length)
{
    length*=sizeof(SInt32);
    ::BlockMove(source+sourceIndex,
                destination+destinationIndex,
                length);
}

[nanopico]

There's a strange instruction:

Code: [Select]

while ((count1 | count2)<minGallop);What's the logic of that? It looks like an error.

That would be a bitwise or of count1 and count2.  Taking the result of that or and comparing it to minGallop

[OS923]

Yes, but why would they want the bitwise or of count1 and count2. That doesn't appear anywhere from the description of the algorithm.

[Protools5LEGuy]

https://francis.naukas.com/2020/07/11/una-red-de-neuronas-artificiales-disena-un-algoritmo-de-ordenacion-que-parece-mas-rapido-que-el-quicksort-de-hoare/

Please use google translate or something similar.

An A.I. neural-net HAS designed a new sorting algorithm fastest than Hoare´s Quicksort

https://arxiv.org/abs/2007.03629

[Protools5LEGuy]

[youtube]ywWBy6J5gz8[/youtube]

[youtube]CmPA7zE8mx0[/youtube]

https://www.meneame.net/story/red-neuronas-artificiales-disena-algoritmo-ordenacion-parece-mas

More chat (in Spanish) about sorting

PM if you prefer not using Youtube links on this post