As part of doing the code for our new picmas tree, I needed to come up with a way to sort a small array of numbers on the Microchip 16F685 processor that we are using. I've looked through a few different sort algorithms and came across the Gnome Sort algorithm on Wikipedia. It was originally created by Dick Grune although his web page is only available on archive.org. The algorithm is ideal for this small processor as it is simple, predictable and uses virtually no memory. The pseudo code for this function is basically:

function gnomeSort(a[0..size-1]) {

i := 1

j := 2

while i < size {

if a[i-1] >= a[i] {

i := j

j := j + 1

} else {

swap a[i-1] and a[i]

i := i - 1

if i = 0 {

i := 1

}

}

}

}

Converting this to the 16F685 is a little more complicated as you only have a single pointer register, but since you are only comparing values next to each other you can load FSR once and just increment/decrement to get to the values. Two other creative tricks that I applied to reduce the code and memory footprint is to reverse the destructive comparison to recover the value to swap and then to use the typical three XOR back and forth to swap the values without an intermediary.

;

; PARAMETERS

; SORT_ARRAY - Array to be sorted

; SORT_LENGTH - Number of bytes in the array to sort

; SORT_J - Temporary variable to hold the end sort pointer

;

; NOTES on implementation

; This uses the typical XOR trick to swap the two array elements

; FSR points to the second of the two array elements that we are comparing.

;

SORT

MOVLWSORT_ARRAY+1

MOVWFFSR ; i = 1

INCFFSR,W

MOVWF SORT_J ; j := 2

SORT_1 ; while i < size

MOVFW INDF ; a[i]

DECF FSR

SUBWF INDF,W

SKPNC

GOTO SORT_2

; if a[i-1] >= a[i]

MOVFW SORT_J ; i := j

MOVWF FSR

SUBLW SORT_ARRAY+SORT_LENGTH-1

SKPC

RETURN

INCF SORT_J,F ; j := j + 1

GOTO SORT_1

SORT_2 ; else

SUBWF INDF,W ; Recover a[i]

XORWF INDF,W ; Swap a[i] and value for a[i-1]

XORWF INDF,F

XORWF INDF,W

INCF FSR ; point to a[i]

MOVWF INDF ; store a[i]

DECF FSR ; i := i - 1

MOVLW SORT_ARRAY

SUBWF FSR,W ; if i = 0

SKPNZ

INCF FSR,F ; i := 1

GOTO SORT_1 ; }

END