
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


The   merge sort   is a recursive sort of order    n*log(n). 

It is notable for having a worst case and average complexity of    O(n*log(n)),    and a best case complexity of    O(n)    (for pre-sorted input).

The basic idea is to split the collection into smaller groups by halving it until the groups only have one element or no elements   (which are both entirely sorted groups).

Then merge the groups back together so that their elements are in order.

This is how the algorithm gets its   divide and conquer   description.



Task

Write a function to sort a collection of integers using the merge sort.



The merge sort algorithm comes in two parts:

   a sort function     and 
   a merge function 

The functions in pseudocode look like this:

function mergesort(m)
   var list left, right, result
   if length(m) ≤ 1
       return m
   else
       var middle = length(m) / 2
       for each x in m up to middle - 1
           add x to left
       for each x in m at and after middle
           add x to right
       left = mergesort(left)
       right = mergesort(right)
       if last(left) ≤ first(right) 
          append right to left
          return left
       result = merge(left, right)
       return result

function merge(left,right)
   var list result
   while length(left) > 0 and length(right) > 0
       if first(left) ≤ first(right)
           append first(left) to result
           left = rest(left)
       else
           append first(right) to result
           right = rest(right)
   if length(left) > 0 
       append rest(left) to result
   if length(right) > 0 
       append rest(right) to result
   return result



See also

   the Wikipedia entry:    merge sort


Note:   better performance can be expected if, rather than recursing until    length(m) ≤ 1,    an insertion sort is used for    length(m)    smaller than some threshold larger than   1.   However, this complicates the example code, so it is not shown here.




 
/* ARM assembly Raspberry PI  */
/*  program mergeSort.s  */
 
 /* REMARK 1 : this program use routines in a include file 
   see task Include a file language arm assembly 
   for the routine affichageMess conversion10 
   see at end of this program the instruction include */
/* for constantes see task include a file in arm assembly */
/************************************/
/* Constantes                       */
/************************************/
.include "../constantes.inc"
 
/*********************************/
/* Initialized data              */
/*********************************/
.data
szMessSortOk:       .asciz "Table sorted.\n"
szMessSortNok:      .asciz "Table not sorted !!!!!.\n"
sMessResult:        .asciz "Value  : @ \n"
szCarriageReturn:   .asciz "\n"
 
.align 4
#TableNumber:      .int   1,11,3,6,2,5,9,10,8,4,7
TableNumber:       .int   10,9,8,7,6,5,4,3,2,1
                   .equ NBELEMENTS, (. - TableNumber) / 4
/*********************************/
/* UnInitialized data            */
/*********************************/
.bss
sZoneConv:            .skip 24
/*********************************/
/*  code section                 */
/*********************************/
.text
.global main 
main:                                              @ entry of program 
 
    ldr r0,iAdrTableNumber                         @ address number table
    mov r1,#0                                      @ first element
    mov r2,#NBELEMENTS                             @ number of élements 
    bl mergeSort
    ldr r0,iAdrTableNumber                         @ address number table
    bl displayTable
 
    ldr r0,iAdrTableNumber                         @ address number table
    mov r1,#NBELEMENTS                             @ number of élements 
    bl isSorted                                    @ control sort
    cmp r0,#1                                      @ sorted ?
    beq 1f                                    
    ldr r0,iAdrszMessSortNok                       @ no !! error sort
    bl affichageMess
    b 100f
1:                                                 @ yes
    ldr r0,iAdrszMessSortOk
    bl affichageMess
100:                                               @ standard end of the program 
    mov r0, #0                                     @ return code
    mov r7, #EXIT                                  @ request to exit program
    svc #0                                         @ perform the system call
 
iAdrszCarriageReturn:     .int szCarriageReturn
iAdrsMessResult:          .int sMessResult
iAdrTableNumber:          .int TableNumber
iAdrszMessSortOk:         .int szMessSortOk
iAdrszMessSortNok:        .int szMessSortNok
/******************************************************************/
/*     control sorted table                                   */ 
/******************************************************************/
/* r0 contains the address of table */
/* r1 contains the number of elements  > 0  */
/* r0 return 0  if not sorted   1  if sorted */
isSorted:
    push {r2-r4,lr}                                    @ save registers
    mov r2,#0
    ldr r4,[r0,r2,lsl #2]
1:
    add r2,#1
    cmp r2,r1
    movge r0,#1
    bge 100f
    ldr r3,[r0,r2, lsl #2]
    cmp r3,r4
    movlt r0,#0
    blt 100f
    mov r4,r3
    b 1b
100:
    pop {r2-r4,lr}
    bx lr                                              @ return 
 
/******************************************************************/
/*         merge                                              */ 
/******************************************************************/
/* r0 contains the address of table */
/* r1 contains first start index
/* r2 contains second start index */
/* r3 contains the last index   */ 
merge:
    push {r1-r8,lr}               @ save registers
    mov r5,r2                     @ init index r2->r5 
1:                                @ begin loop first section
    ldr r6,[r0,r1,lsl #2]         @ load value first section index r1
    ldr r7,[r0,r5,lsl #2]         @ load value second section index r5
    cmp r6,r7
    ble 3f                        @ <=  -> location first section OK
    str r7,[r0,r1,lsl #2]         @ store value second section in first section
    add r8,r5,#1
    cmp r8,r3                     @ end second section ?
    strgt r6,[r0,r5,lsl #2]
    bgt 3f                        @ loop
2:                                @ loop insert element part 1 into part 2
    sub r4,r8,#1
    ldr r7,[r0,r8,lsl #2]         @ load value 2
    cmp r6,r7                     @ value < 
    strlt r6,[r0,r4,lsl #2]       @ store value 
    blt 3f
    str r7,[r0,r4,lsl #2]         @ store value 2
    add r8,#1
    cmp r8,r3                     @ end second section ?
    ble 2b                        @ no loop 
    sub r8,#1
    str r6,[r0,r8,lsl #2]         @ store value 1
3:
    add r1,#1
    cmp r1,r2                     @ end first section ?
    blt 1b
 
100:
    pop {r1-r8,lr}
    bx lr                          @ return 
/******************************************************************/
/*      merge sort                                                */ 
/******************************************************************/
/* r0 contains the address of table */
/* r1 contains the index of first element */
/* r2 contains the number of element */
mergeSort:
    push {r3-r7,lr}           @ save registers
    cmp r2,#2
    blt 100f
    lsr r4,r2,#1             @ number of element of each subset
    tst r2,#1
    addne r4,#1
    mov r5,r1              @ save first element
    mov r6,r2              @ save number of element
    mov r7,r4              @ save number of element of each subset
    mov r2,r4
    bl mergeSort
    mov r1,r7              @ restaur number of element of each subset
    mov r2,r6              @ restaur  number of element
    sub r2,r1
    mov r3,r5              @ restaur first element
    add r1,r3              @ + 1
    bl mergeSort           @ sort first subset
    mov r1,r5              @ restaur first element
    mov r2,r7              @ restaur number of element of each subset
    add r2,r1
    mov r3,r6              @ restaur  number of element
    add r3,r1 
    sub r3,#1              @ last index
    bl merge
100:
    pop {r3-r7,lr}
    bx lr                  @ return 
 
/******************************************************************/
/*      Display table elements                                */ 
/******************************************************************/
/* r0 contains the address of table */
displayTable:
    push {r0-r3,lr}                                    @ save registers
    mov r2,r0                                          @ table address
    mov r3,#0
1:                                                     @ loop display table
    ldr r0,[r2,r3,lsl #2]
    ldr r1,iAdrsZoneConv                               @ 
    bl conversion10S                                    @ décimal conversion 
    ldr r0,iAdrsMessResult
    ldr r1,iAdrsZoneConv                               @ insert conversion
    bl strInsertAtCharInc
    bl affichageMess                                   @ display message
    add r3,#1
    cmp r3,#NBELEMENTS - 1
    ble 1b
    ldr r0,iAdrszCarriageReturn
    bl affichageMess
    mov r0,r2
100:
    pop {r0-r3,lr}
    bx lr
iAdrsZoneConv:           .int sZoneConv
/***************************************************/
/*      ROUTINES INCLUDE                           */
/***************************************************/
.include "../affichage.inc"
 