[Return to Main Page]

Combination Sort by Daryl Rictor
[Up to Source Code Repository]

Combination Sort

This is a sort routine called a Combination Sort, which is a modified bubble sort (iterative) that takes much less time to complete.

As an example, using a 255 element array, the standard bubble sort routine found elsewhere in the repository took on average about 2 seconds to complete on my computer. My routine took about 2/10ths of a second to sort the same data. I used three different random patterns and used my TOD timer to perform the time measurements.

    ;*************************************************************;
    ;                                                             ;
    ; Combination Sort - An improvement on the Bubble Sort        ;
    ;                                                             ;
    ;*************************************************************;
    ;                                                             ;
    ; This idea was presented as a BASIC program in a magazine    ;
    ; article about 12 years ago. I could not find the orginal    ;
    ; article and I do not know who the author was.  I am         ;
    ; including the BASIC routine that I had used in some of my   ;
    ; BASIC programs.                                             ;
    ;                                                             ;
    ; As I recall, this sort routine cuts the processing time by  ;
    ; reducing the size of the array into smaller chuncks, and    ;
    ; moving each elelment more than one position at a time, thus ;
    ; reducing the total number of cycles through the loop.  I    ;
    ; have not seen a faster, non-recursive sort routine.         ;
    ;                                                             ;
    ; I have taken the BASIC routine and converted it to 65C02    ;
    ; assembly code.  I am using the added opcodes PHX, PHY,      ;
    ; PLX, PLY, LDA (zp) & STZ zp to decrease size and increase   ;
    ; speed.  By adding an additional zero page temp variable,    ;
    ; you can use the basic 6502 opcodes to perform this sort.    ;
    ;                                                             ;
    ; Here's my copy of the BASIC Routine:                        ;
    ;                                                             ;
    ; SUB COMBINATION (A())                                       ;
    ;   size = A(0)                                               ;
    ;   gap = A(0)                                                ;
    ;   DO                                                        ;
    ;     gap = INT(gap / 1.3)                                    ;
    ;     IF gap < 1 THEN gap = 1                                 ;
    ;     switch = 0                                              ;
    ;     FOR I = 1 TO size - gap                                 ;
    ;       J = I + gap                                           ;
    ;       IF A(I) > A(J) THEN                                   ;
    ;         SWAP A(I), A(J)                                     ;
    ;         switch = switch + 1                                 ;
    ;       END IF                                                ;
    ;     NEXT I                                                  ;
    ;   LOOP UNTIL gap = 1 AND switch = 0                         ;
    ;                                                             ;
    ;  Daryl Rictor - May 2001                                    ;
    ;                                                             ;
    ;*************************************************************;
    ;
    ;
    ; define variables
    ;
    array    =   $30
    flag     =   $32
    gap      =   $33
    ;
    ;
    ; UPPERCASE opcodes are 6502 codes
    ; lowercase opcodes are 65C02 codes
    ;

    SORT8    lda (array)       ; FETCH ELEMENT COUNT
             STA gap           ; save in gap
    SORTLP   LSR gap           ; divide gap by ~1.3  (gap * 0.7692)
             LDA gap           ; (not critical to be exact)
             LSR A             ; this routine calculates it as:
             CLC               ;
             ADC gap           ;     gap = gap/2 + gap/4
             STA gap           ;     (gap * 0.7500)
             CMP #$00          ;
             BNE CLFLAG        ; if gap = 0 then set it to 1
             INC gap           ;
    CLFLAG   stz flag          ; TURN EXCHANGE FLAG OFF (= 0)
             SEC               ;
             lda (array)       ; get size
             SBC gap           ; subract gap to reduce loop size
             TAX               ; (loop counter & pointer to lower element)
    NXTEL    CLC               ; calc pointer to upper element
             TXA               ;
             ADC gap           ;
             TAY               ; y = x + gap
             LDA (array),y     ; get upper element
             PHA               ; save it for swap
             phy               ; save y for swap
             phx               ; transfer x reg to y reg
             ply               ; get pointer to lower element
             CMP (array),y     ; compare = upper - lower
             BCS CLRSTK        ; if upper < lower, swap elements
             LDA (array),y     ; get lower value
             ply               ; get upper element pointer
             STA (array),y     ; save lower value in upper element
             phx               ; transfer x reg to y reg
             ply               ; get lower element pointer
             PLA               ; get upper value
             STA (array),y     ; save upper vaule in lower element
             LDA #$FF          ; TURN EXCHANGE FLAG ON (= -1)
             STA flag          ;
             BNE CHKEND        ; skip over stack maintenance
    CLRSTK   PLA               ; remove upper element & pointer from stack
             PLA               ;
    CHKEND   DEX               ; END OF LIST?
             BNE NXTEL         ; NO. FETCH NEXT ELEMENT
             LDA gap           ;
             CMP #$01          ;
             BNE SORTLP        ; repeat loop unitl the gap size = 1
             BIT $32           ; if gap = 1, IS EXCHANGE FLAG STILL OFF?
             BMI SORTLP        ; NO. GO THROUGH LIST AGAIN
             RTS               ; YES. LIST IS NOW ORDERED
    ;
    ; end SORT8
    ;
    ;*************************************************************;

Last page update: May 17, 2001.