There is a strong chance this is a quite naive post, anyway...

Looking at compressor sources that involve BWT transformation I always wonder why

instead of a miscellanea of routines they do not use a simple merge sort, so I wrote

an optimized version to handle the worst cases as consecutive characters. I hope it

could be useful.

Two hints:

1) if the array to be sorted is a power of 2 the nrm parameter should be set to True,

otherwise to False;

2) if you need a stable method change the line 77

ELSE IF a[m-1]<=a[i] THEN

into

ELSE IF a[m-1]<a[i] THEN

Code:

PROGRAM Sort;
CONST
len=13;
VAR
a:ARRAY[0..2*len-1] OF Byte;
i,j:Word;
src:Boolean;
PROCEDURE MergeSort(VAR src:Boolean;nrm:Boolean);
VAR
dbl,sub,i,j,k,l,m,n,dst,lim:Word;
x,y,z:Integer;
BEGIN
dbl:=len SHL 1;
sub:=1;
WHILE sub<len DO
BEGIN
i:=0;
j:=sub;
IF src THEN
BEGIN
Inc(i,len);
Inc(j,len);
k:=dbl;
dst:=0;
END
ELSE
BEGIN
k:=len;
dst:=len;
END;
n:=sub SHL 1;
WHILE i<k DO
BEGIN
l:=i+sub;
m:=j+sub;
lim:=dst+n;
IF nrm THEN
BEGIN
x:=sub;
y:=sub;
z:=n;
END
ELSE
BEGIN
IF src THEN
BEGIN
IF l>dbl THEN
l:=dbl;
IF m>dbl THEN
m:=dbl;
IF lim>len THEN
lim:=len;
END
ELSE
BEGIN
IF l>len THEN
l:=len;
IF m>len THEN
m:=len;
IF lim>dbl THEN
lim:=dbl;
END;
x:=l-i;
y:=m-j;
z:=m-i;
END;
IF a[l-1]<=a[j] THEN
BEGIN
IF z>0 THEN
Move(a[i],a[dst],z);
i:=l;
j:=m;
dst:=lim;
END
(* Solo < per avere un metodo stabile *)
ELSE IF a[m-1]<=a[i] THEN
BEGIN
IF y>0 THEN
Move(a[j],a[dst],y)
ELSE
y:=0;
IF x>0 THEN
Move(a[i],a[dst+y],x);
i:=l;
j:=m;
dst:=lim;
END;
WHILE dst<lim DO
BEGIN
x:=a[i];
y:=a[j];
IF (j>=m) OR ((i<l) AND (x<=y)) THEN
BEGIN
a[dst]:=x;
Inc(i);
END
ELSE
BEGIN
a[dst]:=y;
Inc(j);
END;
Inc(dst);
END;
Inc(i,sub);
Inc(j,sub);
END;
sub:=n;
src:=NOT src;
END;
END;
BEGIN
Randomize;
FOR i:=0 TO len-1 DO
a[i]:=Random(256);
FOR i:=0 TO len-1 DO
Write(' ',a[i]);
WriteLn;
src:=False;
MergeSort(src,False);
IF NOT src THEN
j:=0
ELSE
j:=len;
FOR i:=j TO j+len-1 DO
Write(' ',a[i]);
END.