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
MOVLW SORT_ARRAY+1
MOVWF FSR ; i = 1
INCF FSR,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