sorting

Sorting Algorithm

This is a sorting algorithm.   It may be applied to a set of data in order to sort it.    
For comparing various sorts, see compare sorts.  
For other sorting algorithms,   see sorting algorithms,   or:

O(n logn) sorts
Heap sort |
Merge sort |
Patience sort |
Quick sort
O(n log2n) sorts
Shell Sort
O(n2) sorts
Bubble sort |
Cocktail sort |
Cocktail sort with shifting bounds |
Comb sort |
Cycle sort |
Gnome sort |
Insertion sort |
Selection sort |
Strand sort
other sorts
Bead sort |
Bogo sort |
Common sorted list |
Composite structures sort |
Custom comparator sort |
Counting sort |
Disjoint sublist sort |
External sort |
Jort sort |
Lexicographical sort |
Natural sorting |
Order by pair comparisons |
Order disjoint list items |
Order two numerical lists |
Object identifier (OID) sort |
Pancake sort |
Quickselect |
Permutation sort |
Radix sort |
Ranking methods |
Remove duplicate elements |
Sleep sort |
Stooge sort |
[Sort letters of a string] |
Three variable sort |
Topological sort |
Tree sort


Write a function that orders two lists or arrays filled with numbers.
The function should accept two lists as arguments and return true if the first list should be ordered before the second, and false otherwise.

The order is determined by lexicographic order: Comparing the first element of each list.
If the first elements are equal, then the second elements should be compared, and so on, until one of the list has no more elements.
If the first list runs out of elements the result is true.
If the second list or both run out of elements the result is false.

Note: further clarification of lexicographical ordering is expounded on the talk page here and here.

 
/* ARM assembly AARCH64 Raspberry PI 3B */
/*  program orderlist64.s   */
 
/*******************************************/
/* Constantes file                         */
/*******************************************/
/* for this file see task include a file in language AArch64 assembly*/
.include "../includeConstantesARM64.inc" 
 
/*********************************/
/* Initialized data              */
/*********************************/
.data
szMessResult1:      .asciz "List1 < List2 \n"           // message result
szMessResult2:      .asciz "List1 => List2 \n"           // message result
szCarriageReturn:  .asciz "\n"
 
qTabList1:         .quad  1,2,3,4,5
.equ NBELEMENTS1,   (. - qTabList1) /8
qTabList2:         .quad  1,2,1,5,2,2
.equ NBELEMENTS2,   (. - qTabList2) /8
qTabList3:         .quad  1,2,3,4,5
.equ NBELEMENTS3,   (. - qTabList3) /8
qTabList4:         .quad  1,2,3,4,5,6
.equ NBELEMENTS4,   (. - qTabList4) /8
/*********************************/
/* UnInitialized data            */
/*********************************/
.bss 
/*********************************/
/*  code section                 */
/*********************************/
.text
.global main 
main:                                       // entry of program 
    ldr x0,qAdriTabList1
    mov x1,NBELEMENTS1
    ldr x2,qAdriTabList2
    mov x3,NBELEMENTS2
    bl listeOrder
    cmp x0,0                                // false ?
    beq 1f                                  // yes
    ldr x0,qAdrszMessResult1                // list 1 < list 2
    bl affichageMess                        // display message
    b 2f
1:
    ldr x0,qAdrszMessResult2
    bl affichageMess                        // display message
 
2:
    ldr x0,qAdriTabList1
    mov x1,NBELEMENTS1
    ldr x2,qAdriTabList3
    mov x3,NBELEMENTS3
    bl listeOrder
    cmp x0,0                               // false ?
    beq 3f                                  // yes
    ldr x0,qAdrszMessResult1                // list 1 < list 2
    bl affichageMess                        // display message
    b 4f
3:
    ldr x0,qAdrszMessResult2
    bl affichageMess                        // display message
4:
    ldr x0,qAdriTabList1
    mov x1,NBELEMENTS1
    ldr x2,qAdriTabList4
    mov x3,NBELEMENTS4
    bl listeOrder
    cmp x0,0                               // false ?
    beq 5f                                  // yes
    ldr x0,qAdrszMessResult1                // list 1 < list 2
    bl affichageMess                        // display message
    b 6f
5:
    ldr x0,qAdrszMessResult2
    bl affichageMess                        // display message
6:
100:                                        // standard end of the program 
    mov x0,0                              // return code
    mov x8,EXIT                           // request to exit program
    svc 0                                  // perform the system call
qAdriTabList1:             .quad qTabList1
qAdriTabList2:             .quad qTabList2
qAdriTabList3:             .quad qTabList3
qAdriTabList4:             .quad qTabList4
qAdrszMessResult1:         .quad szMessResult1
qAdrszMessResult2:         .quad szMessResult2
qAdrszCarriageReturn:      .quad szCarriageReturn
/******************************************************************/
/*     liste order                                                */ 
/******************************************************************/
/* x0 contains the address of list 1 */
/* x1 contains list 1 size           */
/* x2 contains the address of list 2 */
/* x3 contains list 2 size           */
/* x0 returns 1 if list1 < list2     */
/* x0 returns 0 else                 */
listeOrder:
    stp x1,lr,[sp,-16]!          // save  registers
    stp x2,x3,[sp,-16]!          // save  registers
    cbz x1,99f                    // list 1 size = zero ?
    cbz x3,98f                    // list 2 size = zero ?
 
    mov x4,#0                    // index list 1
    mov x5,#0                    // index list 2
1:
    ldr x6,[x0,x4,lsl #3]        // load list 1 element
    ldr x8,[x2,x5,lsl #3]        // load list 2 element
    cmp x6,x8                    // compar
    bgt 4f
    beq 2f                       // list 1 = list 2
    add x4,x4,1                  // increment index 1
    cmp x4,x1                    // end list ?
    bge 5f
    b 1b                         // else loop
2:
    add x4,x4,1                  // increment index 1
    cmp x4,x1                    // end list ?
    bge 3f                       // yes -> verif size
    add x5,x5,1                  // else increment index 2
    cmp x5,x3                    // end list 2 ?
    bge 4f
    b 1b                         // else loop
3:
    cmp x1,x3                     // compar size
    bge 4f                       // list 2 < list 1
    blt 5f                       // list 1 < list 2
    b 100f
4:
    mov x0,#0                    // list 1 > list 2
    b 100f
5:
    mov x0,#1                    //  list 1 < list 2
    b 100f
98:                              // error
    mov x0,-2
    b 100f
99:                              // error
    mov x0,-1
100:
    ldp x2,x3,[sp],16            // restaur  2 registers
    ldp x1,lr,[sp],16            // restaur  2 registers
    ret                          // return to address lr x30
/********************************************************/
/*        File Include fonctions                        */
/********************************************************/
/* for this file see task include a file in language AArch64 assembly */
.include "../includeARM64.inc"
 
 