Sorting in Small Memories

Dr. Carlo Pescio
Sorting in Small Memories

Published in Electronic Design, Penton Publishing, Vol. 44 No. 8, April 15, 1996.
This paper won the "Best of the Issue" award.

Sorting is an essential routine used in most programs; still, in embedded applications we often have to struggle with extremely small memory for code and auxiliary data, including stack space. Saving memory raises new challenges even in well-known areas like sorting, since we can’t always trade performance for space. The following implementation of the CombSort algorithm (average performance quite higher than BubbleSort, but lower than QuickSort) has been filed down to a very small footprint, while providing good performance in sorting arrays of integers using low-end Intel processors; here are the major features of the routine:

It is callable from C language using small model: segment registers, as well as SI, DI, BP, SP are all preserved.
Code is 52 bytes long and is ROM-able.
10 bytes of stack needed at run-time, including parameters.
Uses only standard 8086 instructions.
Is adaptable to sort an array of signed or unsigned integers.

Although optimized for size, the CombSort algorithm is quite fast, and this tight implementation may even outperform a QuickSort routine implemented in high-level languages. If your target processor is a 386 or more, it is even possible to create a smaller and faster version of the program, although applications using a 386 are usually not memory-constrained.

The listing if fully commented with strategic and tactical annotations, so you can borrow some of the techniques used here and apply them to other problems, where saving memory is an essential part of the coding activity. I also include a short C program to show how to call the routine from C language.

An example of call in C language:

#include <stdio.h>

extern void sort( int size, int gap, int x[] ) ;
/* always call with size = gap */

int main()
  {
  #define SIZE 6
  int a[ SIZE ] = { 2, 5, 3, -6, 8, 1 } ;
  int i ;
  sort( SIZE, SIZE, a ) ;
  for( i = 0; i < SIZE; i++ )
    printf( "%d ", a[ i ] ) ;
  return( 0 ) ;
  }

The assembly code:

.model small
.code

public	_sort	; C prototype: void sort( int size, int gap, int data[] )
				; call using size = gap, size > 0
top:
	push	di		; must save value (used by C compilers)
	mov	dx, ax		; dx used as a "swap done" flag
	; prepare pointers to items to compare
	shl	ax, 1		; must index integers = 2 bytes in size
	mov	di, ax	
swapping:
	; swap [bx], [bx+di] if necessary
	mov	ax, [bx]
	cmp	ax, [bx+di]
	jle	already_sorted	; use jbe for unsigned integers sort
	; swap
	xchg	ax, [bx+di]
	xchg	ax, [bx]
	xor	dx, dx		; dx=gap if no swapping took place, 0 otherwise
already_sorted:
	; point to next items
	inc	bx
	inc	bx
	loop	swapping
	pop	di		; must restore now

	; if no switches made and gap = 1, items are all sorted
	; condition above is dx = gap and gap = 1
	; that means I can simply check for dx = 1
	dec	dx
	jz	all_sorted
_sort:
	pop	dx		; get return address
	pop	cx		; get size
	pop	ax		; get gap
	
	; a good approximation of gap = max( 1, gap / 1.3 )
	mov	bx, ax
	shr	bx, 1
	shr	bx, 1
	sub	ax, bx
	dec	ax
	jnz	gap_ok
	inc	ax
gap_ok:
	pop	bx		; get data address

	; here the stack is restored to the former, only the gap 
	; is changed to the next value, so I can iterate many 
	; times by falling into _sort from swapping.
	push	bx		; save data address
	push	ax		; save new gap
	push	cx		; save size
	push	dx		; save return address

	; iterate size - gap times
	sub	cx, ax
	jg	top		; if more than 1 element to sort

all_sorted:	
	ret
end

Biography
Carlo Pescio holds a doctoral degree in Computer Science and is a consultant and mentor for various European companies and corporations, including the Directorate of the European Commission. He specializes in object oriented technologies and is a member of IEEE Computer Society, the ACM, and the New York Academy of Sciences. He lives in Savona, Italy and can be contacted at pescio@eptacom.net.