I forgot a
if (breakOuter)
{
break;
}
or two.
This version works correctly with (count1 + count2):
#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();
};
#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);
}