summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--grailsort_ref.c155
1 files changed, 19 insertions, 136 deletions
diff --git a/grailsort_ref.c b/grailsort_ref.c
index 0a95076..b2c53f4 100644
--- a/grailsort_ref.c
+++ b/grailsort_ref.c
@@ -19,8 +19,6 @@
#define SORT_TYPE int
static cmpfun SORT_CMP;
-#define GRAIL_EXT_BUFFER_LENGTH 512
-
static inline void grail_swap1(SORT_TYPE *a,SORT_TYPE *b){
SORT_TYPE c=*a;
*a=*b;
@@ -177,126 +175,22 @@ static void grail_SmartMergeWithoutBuffer(SORT_TYPE *arr,int *alen1,int *atype,i
*alen1=len2; *atype=ftype;
}
-/***** Sort With Extra Buffer *****/
-
-// arr[M..-1] - free, arr[0,L1-1]++arr[L1,L1+L2-1] -> arr[M,M+L1+L2-1]
-static void grail_MergeLeftWithXBuf(SORT_TYPE *arr,int L1,int L2,int M){
- int p0=0,p1=L1; L2+=L1;
- while(p1<L2){
- if(p0==L1 || SORT_CMP(arr+p0,arr+p1)>0) arr[M++]=arr[p1++];
- else arr[M++]=arr[p0++];
- }
- if(M!=p0) while(p0<L1) arr[M++]=arr[p0++];
-}
-
-static void grail_SmartMergeWithXBuf(SORT_TYPE *arr,int *alen1,int *atype,int len2,int lkeys){
- int p0=-lkeys,p1=0,p2=*alen1,q1=p2,q2=p2+len2;
- int ftype=1-*atype; // 1 if inverted
- while(p1<q1 && p2<q2){
- if(SORT_CMP(arr+p1,arr+p2)-ftype<0) arr[p0++]=arr[p1++];
- else arr[p0++]=arr[p2++];
- }
- if(p1<q1){
- *alen1=q1-p1;
- while(p1<q1) arr[--q2]=arr[--q1];
- } else{
- *alen1=q2-p2;
- *atype=ftype;
- }
-}
-
-// arr - starting array. arr[-lblock..-1] - buffer (if havebuf).
-// lblock - length of regular blocks. First nblocks are stable sorted by 1st elements and key-coded
-// keys - arrays of keys, in same order as blocks. key<midkey means stream A
-// nblock2 are regular blocks from stream A. llast is length of last (irregular) block from stream B, that should go before nblock2 blocks.
-// llast=0 requires nblock2=0 (no irregular blocks). llast>0, nblock2=0 is possible.
-static void grail_MergeBuffersLeftWithXBuf(SORT_TYPE *keys,SORT_TYPE *midkey,SORT_TYPE *arr,int nblock,int lblock,int nblock2,int llast){
- int l,prest,lrest,frest,pidx,cidx,fnext,plast;
-
- if(nblock==0){
- l=nblock2*lblock;
- grail_MergeLeftWithXBuf(arr,l,llast,-lblock);
- return;
- }
-
- lrest=lblock;
- frest=SORT_CMP(keys,midkey)<0 ? 0 : 1;
- pidx=lblock;
- for(cidx=1;cidx<nblock;cidx++,pidx+=lblock){
- prest=pidx-lrest;
- fnext=SORT_CMP(keys+cidx,midkey)<0 ? 0 : 1;
- if(fnext==frest){
- memcpy(arr+prest-lblock,arr+prest,lrest*sizeof(SORT_TYPE));
- prest=pidx;
- lrest=lblock;
- } else{
- grail_SmartMergeWithXBuf(arr+prest,&lrest,&frest,lblock,lblock);
- }
- }
- prest=pidx-lrest;
- if(llast){
- plast=pidx+lblock*nblock2;
- if(frest){
- memcpy(arr+prest-lblock,arr+prest,lrest*sizeof(SORT_TYPE));
- prest=pidx;
- lrest=lblock*nblock2;
- frest=0;
- } else{
- lrest+=lblock*nblock2;
- }
- grail_MergeLeftWithXBuf(arr+prest,lrest,llast,-lblock);
- } else{
- memcpy(arr+prest-lblock,arr+prest,lrest*sizeof(SORT_TYPE));
- }
-}
-
-/***** End Sort With Extra Buffer *****/
-
// build blocks of length K
// input: [-K,-1] elements are buffer
// output: first K elements are buffer, blocks 2*K and last subblock sorted
-static void grail_BuildBlocks(SORT_TYPE *arr,int L,int K,SORT_TYPE *extbuf,int LExtBuf){
- int m,u,h,p0,p1,rest,restk,p,kbuf;
- kbuf=K<LExtBuf ? K : LExtBuf;
- while(kbuf&(kbuf-1)) kbuf&=kbuf-1; // max power or 2 - just in case
+static void grail_BuildBlocks(SORT_TYPE *arr,int L,int K){
+ int m,u,h,p0,p1,rest,restk,p;
- if(kbuf){
- memcpy(extbuf,arr-kbuf,kbuf*sizeof(SORT_TYPE));
- for(m=1;m<L;m+=2){
- u=0;
- if(SORT_CMP(arr+(m-1),arr+m)>0) u=1;
- arr[m-3]=arr[m-1+u];
- arr[m-2]=arr[m-u];
- }
- if(L%2) arr[L-3]=arr[L-1];
- arr-=2;
- for(h=2;h<kbuf;h*=2){
- p0=0;
- p1=L-2*h;
- while(p0<=p1){
- grail_MergeLeftWithXBuf(arr+p0,h,h,-h);
- p0+=2*h;
- }
- rest=L-p0;
- if(rest>h){
- grail_MergeLeftWithXBuf(arr+p0,h,rest-h,-h);
- } else {
- for(;p0<L;p0++) arr[p0-h]=arr[p0];
- }
- arr-=h;
- }
- memcpy(arr+L,extbuf,kbuf*sizeof(SORT_TYPE));
- } else{
- for(m=1;m<L;m+=2){
- u=0;
- if(SORT_CMP(arr+(m-1),arr+m)>0) u=1;
- grail_swap1(arr+(m-3),arr+(m-1+u));
- grail_swap1(arr+(m-2),arr+(m-u));
- }
- if(L%2) grail_swap1(arr+(L-1),arr+(L-3));
- arr-=2;
- h=2;
+ for(m=1;m<L;m+=2){
+ u=0;
+ if(SORT_CMP(arr+(m-1),arr+m)>0) u=1;
+ grail_swap1(arr+(m-3),arr+(m-1+u));
+ grail_swap1(arr+(m-2),arr+(m-u));
}
+ if(L%2) grail_swap1(arr+(L-1),arr+(L-3));
+ arr-=2;
+ h=2;
+
for(;h<K;h*=2){
p0=0;
p1=L-2*h;
@@ -399,7 +293,7 @@ static void grail_LazyStableSort(SORT_TYPE *arr,int L){
// keys are on the left of arr. Blocks of length LL combined. We'll combine them in pairs
// LL and nkeys are powers of 2. (2*LL/lblock) keys are guarantied
-static void grail_CombineBlocks(SORT_TYPE *keys,SORT_TYPE *arr,int len,int LL,int lblock,bool havebuf,SORT_TYPE *xbuf){
+static void grail_CombineBlocks(SORT_TYPE *keys,SORT_TYPE *arr,int len,int LL,int lblock,bool havebuf){
int M,nkeys,b,NBlk,midkey,lrest,u,p,v,kc,nbl2,llast;
SORT_TYPE *arr1;
@@ -410,7 +304,7 @@ static void grail_CombineBlocks(SORT_TYPE *keys,SORT_TYPE *arr,int len,int LL,in
len-=lrest;
lrest=0;
}
- if(xbuf) memcpy(xbuf,arr-lblock,lblock*sizeof(SORT_TYPE));
+
for(b=0;b<=M;b++){
if(b==M && lrest==0) break;
arr1=arr+b*2*LL;
@@ -434,17 +328,13 @@ static void grail_CombineBlocks(SORT_TYPE *keys,SORT_TYPE *arr,int len,int LL,in
if(llast!=0){
while(nbl2<NBlk && SORT_CMP(arr1+NBlk*lblock,arr1+(NBlk-nbl2-1)*lblock)<0) nbl2++;
}
- if(xbuf) grail_MergeBuffersLeftWithXBuf(keys,keys+midkey,arr1,NBlk-nbl2,lblock,nbl2,llast);
- else grail_MergeBuffersLeft(keys,keys+midkey,arr1,NBlk-nbl2,lblock,havebuf,nbl2,llast);
+ grail_MergeBuffersLeft(keys,keys+midkey,arr1,NBlk-nbl2,lblock,havebuf,nbl2,llast);
}
- if(xbuf){
- for(p=len;--p>=0;) arr[p]=arr[p-lblock];
- memcpy(arr-lblock,xbuf,lblock*sizeof(SORT_TYPE));
- }else if(havebuf) while(--len>=0) grail_swap1(arr+len,arr+len-lblock);
+ if(havebuf) while(--len>=0) grail_swap1(arr+len,arr+len-lblock);
}
-static void grail_commonSort(SORT_TYPE *arr,int Len,SORT_TYPE *extbuf,int LExtBuf){
+static void grail_commonSort(SORT_TYPE *arr,int Len){
int lblock,nkeys,findkeys,ptr,cbuf,lb,nk;
bool havebuf,chavebuf;
long long s;
@@ -471,8 +361,7 @@ static void grail_commonSort(SORT_TYPE *arr,int Len,SORT_TYPE *extbuf,int LExtBu
}
ptr=lblock+nkeys;
cbuf=havebuf ? lblock : nkeys;
- if(havebuf) grail_BuildBlocks(arr+ptr,Len-ptr,cbuf,extbuf,LExtBuf);
- else grail_BuildBlocks(arr+ptr,Len-ptr,cbuf,NULL,0);
+ grail_BuildBlocks(arr+ptr,Len-ptr,cbuf);
// 2*cbuf are built
while(Len-ptr>(cbuf*=2)){
@@ -490,21 +379,15 @@ static void grail_commonSort(SORT_TYPE *arr,int Len,SORT_TYPE *extbuf,int LExtBu
}
lb=(2*cbuf)/nk;
}
- } else{
-#if 0
- if(LExtBuf!=0){
- while(lb>LExtBuf && lb*lb>2*cbuf) lb/=2; // set size of block close to sqrt(new_block_length)
- }
-#endif
}
- grail_CombineBlocks(arr,arr+ptr,Len-ptr,cbuf,lb,chavebuf,chavebuf && lb<=LExtBuf ? extbuf : NULL);
+ grail_CombineBlocks(arr,arr+ptr,Len-ptr,cbuf,lb,chavebuf);
}
grail_SortIns(arr,ptr);
grail_MergeWithoutBuffer(arr,ptr,Len-ptr);
}
static void GrailSort(SORT_TYPE *arr,int Len){
- grail_commonSort(arr,Len,NULL,0);
+ grail_commonSort(arr,Len);
}
void grailsort_ref(void *base, size_t nmel, size_t width, cmpfun cmp)
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-14 22:42:42 +0000