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 := 2SORT_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_1SORT_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`