Bidirectional bubble sort

Bidirectional bubble sort is a variation to the well known bubble sort but adds an extra level of efficiency in terms of speed.
It iterates through the list of elements not only from the beginning to the end as the bubble sort does but  also from the end to beginning in reverse order, reducing the overall sorting time by dynamically limiting the number of elements being iterated through.
It is also known as cocktail shaker sort, shaker sort, double-direction bubble sort and is also an “in place sorting algorithm” which means that no extra RAM memory is needed to sort the list elements.
The bidirectional bubble sort works by (1)iterating up the array to be sorted from the first element to the last, comparing each pair of elements and swapping their positions if necessary. The last swap index position is remembered to become the next upper limit of forward iteration.(2)Right after the forward iteration, follows a backward iteration starting  from last upper index down to the lower index limit comparing each pair of elements and swapping their positions if necessary.The last swap index position is remembered to become the next lower limit of the backward iteration.The whole 2 step cycle repeats itself until the two limits - upper and lower - become equal.
Let us see an example of sorting an array to make the idea of bidirectional bubble sort clearer, using AVR assembler to implement it.
Unordered list.
{12, 0, 13, 5, 16, 0, 17, 18}

Forward iteration.

During the first forward iteration the initial upper and lower limits are index #7 and #0 respectively. The iteration will start from the lower index limit which happens to be #0 in the beginning.

Number 16 will bubble up, swapping up since it is the biggest number in the iteration.The iteration will stop when the upper index limit is reached.

As a result the upper index limit will change to #5(the last index where a swap happened) as indexes above it are already sorted.

Backward iteration.

The backward iteration starts from the upper index limit down to lower index limit swapping adjacent numbers if necessary.

Number 0(index #4) will bubble down, swapping all the way down since it is the smallest number in this iteration.

As a result the lower index limit will change to #1(the last index where a swap happened) as indexes under it are already sorted.

The same sequence of forward and backward iteration repeats until the lower and upper index limit become the same(equal).

Implementation.
Avr assembler implementation is prepared for 8  and 16 bits signed and unsigned numbers.

Signed 1 byte Bi-Directional Bubble sort.

#define BUFFER_SIZE 256

#define INDEX_LIMIT BUFFER_SIZE-1   ;zero based index

.dseg
buffer:  .byte BUFFER_SIZE

.cseg

/************************8 bit Sigend Bi-directional Bubble Sort*************
;Sort unsigned bytes between 0 and 255
@AUTHOR: Sergey Iliev
@INPUT:RAM buffer to sort
@USAGE: right,left,k,cnt,axl,bxl,
Z - buffer item pointer
@OUTPUT: RAM buffer sorted out
**************************************************************/

Signed8bitBiDirectBubbleSort:
ldi    right,INDEX_LIMIT    ;size of array - 1
ldi    left,0

sbbsort:
clr k

;first loop iterate forward
ldi    ZL,low(BUFFER)
ldi    ZH,high(BUFFER)

clr temp
mov cnt,left

sbb_loopr:
ld axl,Z+
ld bxl,Z
cp bxl,axl
brge sbb_loopr1  ;signed
st -Z,bxl
st Z,axl
mov k,cnt
sbb_loopr1:
inc cnt
cp cnt,right
brlo sbb_loopr

mov right,k
ldi cnt,INDEX_LIMIT
mov k,cnt

;exit if no sawp happened or first position swap
tst right
brne sbb_loopl0
ret

sbb_loopl0:
;second loop iterate backward
ldi    ZL,low(BUFFER)
ldi    ZH,high(BUFFER)

clr temp
mov cnt,right
sbb_loopl:
ld axl,Z
ld bxl,-Z
cp bxl,axl
brlt sbb_loopl1 ;signed
st Z,axl
std Z+1,bxl
mov k,cnt
sbb_loopl1:

dec cnt
cp left,cnt
brlo sbb_loopl

mov left,k

cp left,right
brlo sbbsort
ret

Unsigned 1 byte Bi-Directional Bubble sort.

/************************8 bit Unsigend Bi-directional Bubble Sort*************
;Sort unsigned bytes between 0 and 255
@AUTHOR: Sergey Iliev
@INPUT:RAM buffer to sort
@USAGE: right,left,k,cnt,axl,bxl,
Z - buffer item pointer
@OUTPUT: RAM buffer sorted out
**************************************************************/

Unsigned8bitBiDirectBubbleSort:
ldi    right,INDEX_LIMIT    ;size of array - 1
ldi    left,0

ubbsort:
clr k

;first loop iterate forward
ldi    ZL,low(BUFFER)
ldi    ZH,high(BUFFER)

clr temp
mov cnt,left

ubb_loopr:
ld axl,Z+
ld bxl,Z
cp bxl,axl
brsh ubb_loopr1  ;unsigned
st -Z,bxl
st Z,axl
mov k,cnt
ubb_loopr1:
inc cnt
cp cnt,right
brlo ubb_loopr

mov right,k
ldi cnt,INDEX_LIMIT
mov k,cnt

;exit if no sawp happened or first position swap
tst right
brne ubb_loopl0
ret

ubb_loopl0:
;second loop iterate backward
ldi    ZL,low(BUFFER)
ldi    ZH,high(BUFFER)

clr temp
mov cnt,right
ubb_loopl:
ld axl,Z
ld bxl,-Z
cp bxl,axl
brlo ubb_loopl1 ;unsigned
st Z,axl
std Z+1,bxl
mov k,cnt
ubb_loopl1:

dec cnt
cp left,cnt
brlo ubb_loopl

mov left,k

cp left,right
brlo ubbsort
ret

Signed 2 byte Bi-Directional Bubble sort.

#define BUFFER_SIZE16  520

#define INDEX_LIMIT16 BUFFER_SIZE16-1   ;zero based index

.dseg
buffer16:  .byte BUFFER_SIZE16*2

.cseg
/****************16 bit Signed Bi-Directional Bubble/Coctail/Shuffle Sort************

*@AUTHOR: Sergey Iliev
*@INPUT:RAM buffer with unsigned words to sort
*@USAGE:Z - pointer to buffer beginning
rightl,righth - marks the last index(rightmost) 2 adjacent numbers have been exchanged
leftl,lefth   - marks the last index(leftmost) 2 adjacent numbers have been exchanged
cntl:cnth - index
axl:axh,bxl:bxh - words to compare
kxl:kxh - help variable
*@OUTPUT:RAM buffer sorted out!
*****************************************************************************************/
Signed16bitBiDirectBubbleSort:
ldi rightl,low(INDEX_LIMIT16)    ;size of array - 1
ldi righth,high(INDEX_LIMIT16)

//set lower address boundery
ldi leftl,low(0)
ldi lefth,high(0)

sbbsort16:
;prepare for left to right itteration
clr kh
clr kl

;first loop iterate forward
ldi    ZL,low(BUFFER16)
ldi    ZH,high(BUFFER16)

mov cnth,lefth
mov cntl,leftl

;position to the left-most un-ordered element
LSL16 cnth,cntl    ;multiply by 2 ->dealing with 2 bytes/word content

;restore cnt
mov cnth,lefth
mov cntl,leftl

sbb_loopr16:
ld axl,Z+
ld axh,Z+

ld bxl,Z
ldd bxh,Z+1

CP16 bxl,bxh,axl,axh
brge sbb_loopr116       ;signed

st -Z,bxh     ;exchange words
st -Z,bxl

st Z,axl
std Z+1,axh

;remember last rightmost unordered position
mov kl,cntl
mov kh,cnth
sbb_loopr116:

;did it get to the last previously unordered position
CP16 cntl,cnth,rightl,righth
brlo sbb_loopr16

mov rightl,kl
mov righth,kh

;exit if no sawp happened or first position swap
CPI16 rightl,righth,cntl,0
brne sbb_loopl0
ret

;----------------reverse iteration----------------------------

sbb_loopl0:
;prepare for the right to left iterration
ldi    ZL,low(BUFFER16)
ldi    ZH,high(BUFFER16)

mov kl,rightl
mov kh,righth

mov cntl,rightl
mov cnth,righth

;second loop iterate backward
LSL16 cnth,cntl    ;multiply by 2 ->dealing with 2 bytes/word content

//restore cnt
mov cntl,rightl
mov cnth,righth

sbb_loopl16:
ldd axh,Z+1
ld axl,Z

ld bxh,-Z
ld bxl,-Z

CP16 bxl,bxh,axl,axh
brlt sbb_loopl116 ;signed

st Z+,axl
st Z+,axh

st Z,bxl
std Z+1,bxh

;remember last leftmost unordered position
mov kl,cntl
mov kh,cnth
sbb_loopl116:

;did it get to the last previously unordered position
CP16 leftl,lefth,cntl,cnth
brlo sbb_loopl16

mov leftl,kl
mov lefth,kh

CP16 leftl,lefth,rightl,righth
brlo asbbsort16
ret
asbbsort16:
rjmp sbbsort16

Unsigned 2 byte Bi-Directional Bubble sort.

/******************16 bit Unsigned Bi-Directional Bubble/Coctail/Shuffle Sort*********
*@AUTHOR: Sergey Iliev
*@INPUT:RAM buffer with unsigned words to sort
*@USAGE:Z - pointer to buffer beginning
rightl,righth - marks the last index(rightmost) 2 adjacent numbers have been exchanged
leftl,lefth   - marks the last index(leftmost) 2 adjacent numbers have been exchanged
cntl:cnth - index
axl:axh,bxl:bxh - words to compare
kxl:kxh - help variable
*@OUTPUT:RAM buffer sorted out!
*****************************************************************************************/

Unsigned16bitBiDirectBubbleSort:
ldi rightl,low(INDEX_LIMIT16)    ;size of array - 1
ldi righth,high(INDEX_LIMIT16)

//set lower address boundery
ldi leftl,low(0)
ldi lefth,high(0)

ubbsort16:
;prepare for left to right itteration
clr kh
clr kl

;first loop iterate forward
ldi    ZL,low(BUFFER16)
ldi    ZH,high(BUFFER16)

mov cnth,lefth
mov cntl,leftl

;position to the left-most un-ordered element
LSL16 cnth,cntl    ;multiply by 2 ->dealing with 2 bytes/word content

;restore cnt
mov cnth,lefth
mov cntl,leftl

ubb_loopr16:
ld axl,Z+
ld axh,Z+

ld bxl,Z
ldd bxh,Z+1

CP16 bxl,bxh,axl,axh
brsh ubb_loopr116       ;unsigned

st -Z,bxh     ;exchange words
st -Z,bxl

st Z,axl
std Z+1,axh

;remember last rightmost unordered position
mov kl,cntl
mov kh,cnth
ubb_loopr116:

;did it get to the last previously unordered position
CP16 cntl,cnth,rightl,righth
brlo ubb_loopr16

mov rightl,kl
mov righth,kh

;exit if no sawp happened or first position swap
CPI16 rightl,righth,cntl,0
brne ubb_loopl0
ret

;----------------reverse iteration----------------------------

ubb_loopl0:
;prepare for the right to left iterration
ldi    ZL,low(BUFFER16)
ldi    ZH,high(BUFFER16)

mov kl,rightl
mov kh,righth

mov cntl,rightl
mov cnth,righth

;second loop iterate backward
LSL16 cnth,cntl    ;multiply by 2 ->dealing with 2 bytes/word content

//restore cnt
mov cntl,rightl
mov cnth,righth

ubb_loopl16:
ldd axh,Z+1
ld axl,Z

ld bxh,-Z
ld bxl,-Z

CP16 bxl,bxh,axl,axh
brlo ubb_loopl116 ;unsigned

st Z+,axl
st Z+,axh

st Z,bxl
std Z+1,bxh

;remember last leftmost unordered position
mov kl,cntl
mov kh,cnth
ubb_loopl116: