Heap sort

`Heapsort is another in place sorting algorithm suitable for small RAM devices.HeapThe heap data structure is an array that is viewed as a binary tree. Fig.1 shows the heap `
`represented as a binary tree and a regular array. Each node of the tree corresponds to an `
`element of the array A[] that stores the value of the tree node.`

`The number above the node is the corresponding index in the array. The tree is logically viewed as `
`parent child construct as parents are always positioned to the left of their children.A[1] is the root of the tree and given the index i of a node its parent PARENT(i) and left child LEFT(i) `
`and right child RIGHT(i) can be calculated by the following equations.`
`PARENT(i) return [i/2]LEFT(i) return [2*i]RIGHT(i) return [2*i+1]`

`Heap property`
`Heap sort is based upon the so called heap property which for a max-heap(array is sorted from `
`left to right in increasing order) is represented by the following equation.A[PARENT(i)]>=A[i]in other words every node i other then the root, its value is at most the value of its parent thus the `
`largest value in a max-heap is stored at the root.A min-heap is organized the opposite way but the implementation is for max-heap so it will not be discussed here.`

`Max-heapify procedure`
`Maintaining the max-heap property is an important part of the algorithm so here is a visual diagram of its inner working.`

`A[2] at node i=2 violate the max heap property since it is not larger then its both children(LEFT=A[4] and RIGHT=A[5])`

The max heap property is restored by swapping A[2] with A[4], which in turn destroys the max heap property for node 4.

`The max heap property is restored for node 4 but it destroyed the previously fixed property for node 2. `
`The recursive nature of the algorithm will fix it thus allowing the bigger values for this particular branch to `
`float up and smaller ones - float down.Building the max-heap property for all nodes of the tree yields the following arrangement.`

`Heap sort`
`Now that the array is max-heap property compliant, the real sorting can begin.Since the maximum value of the array floated up to the top, it can be put to its right position by `
`exchanging it with the last element(A[1] switches places with A[n]). Unfortunately the switch will destroy the max-heap `
`property of the tree for array element A[1]. All that is needed to restore max - heap property is to go through the same process `
`described above for array elements A[1] through A[n-1]. Observe that for each iteration the size of unordered elements in the `
`array decreases by 1.The heap sort algorithm `

`repeats this process `

`until the subarray length of unsorted elements reaches 0.The following is the implementation of heap sort in avr assembler for 8 and 16 bit signed/unsigned numbers.`
`Unsigned 8 bit heap sort`
`/*------------------8 bit Unsigned Heap Sort----------------------------------@INPUT BUFFER_SIZE - size of the buffer to sort@USAGE: Z - pointer to RAM buffer element Y - pointer to RAM buffer element i - index root - index helper  heapsize - index limit axl,bxl - bytes to compare@OUTPUT:RAM buffer sorted out!----------------------------------------------------------------------------*/Unsigned8bitHeapSortEx://Building the heap (BUFFER_SIZE/2)   mov root,BUFFER_SIZE  lsr root   mov heapsize,BUFFER_SIZEuforloop: mov i,root  rcall Unsigned8maxheapify  dec root  cpi root,1  brsh uforloop//heap sort mov i,BUFFER_SIZE  mov root,BUFFER_SIZE  mov heapsize,BUFFER_SIZEuheapsortloop:  //swap A[1] and A[i] ;first and last  ldi ZL,low(buffer)  ldi ZH,high(buffer)  adiw ZH:ZL,1  ld ax,-Z  ldi YL,low(buffer)  ldi YH,high(buffer)  clr temp  ADD16 YL,YH,root,temp  ld bx,-Y  st Z,bx  st Y,ax	  //heap-size[A]=heap-size[A]-1  dec heapsize  ldi i,1  rcall Unsigned8maxheapify  dec root  cpi root,2  brsh uheapsortloop ret/******8 bit Unsigned Max Heapify****************Maintain max-heap property for unsigned 8 bit@INPUT heapsize - size of the sub-buffer to sort i - index into the array@USAGE: Z - pointer to RAM buffer element Y - pointer to RAM buffer element l - LEFT(i) r - RIGHT(i) temp,largest - temporary axl,bxl - bytes to compare@OUTPUT:Maintain heap property at A[i]*/Unsigned8maxheapify: ;check if lsl overflows the byte boundery  cpi i,0b10000000  brlo boundary retboundary:  mov l,i  lsl l  mov r,i  lsl r  inc r //if l<=heap_size[A]  cp heapsize,l  brlo umaxl   //A[l]  ldi ZL,low(buffer)  ldi ZH,high(buffer)  clr temp  ADD16 ZL,ZH,l,temp  ld ax,-Z //A[i]  ldi ZL,low(buffer)  ldi ZH,high(buffer)  clr temp  ADD16 ZL,ZH,i,temp  ld bx,-Z //if A[i]<A[l]  cp bx,ax  brsh umaxl   mov largest,l  rjmp umaxlonumaxl: //largest<-i  mov largest,iumaxlon: //do the same for the right  //if r<=heap_size[A]  cp heapsize,r  brlo umaxr //A[r]  ldi ZL,low(buffer)  ldi ZH,high(buffer)  clr temp  ADD16 ZL,ZH,r,temp  ld ax,-Z //A[largest]  ldi ZL,low(buffer)  ldi ZH,high(buffer)  clr temp  ADD16 ZL,ZH,largest,temp  ld bx,-Z //A[r]>A[largest]  cp bx,ax  brsh umaxr mov largest,rumaxr: //if largest!=i  cp largest,i  breq umaxend //swap  ldi ZL,low(buffer)  ldi ZH,high(buffer)  clr temp  ADD16 ZL,ZH,i,temp  ld ax,-Z  ldi YL,low(buffer)  ldi YH,high(buffer)  clr temp  ADD16 YL,YH,largest,temp  ld bx,-Y  st Z,bx  st Y,ax //prepare next iteration  mov i,largest  rjmp Unsigned8maxheapifyumaxend:ret`

`Signed 8 bit heap sort`
`/*------------------8 bit Signed Heap Sort----------------------------------@INPUT BUFFER_SIZE - size of the buffer to sort@USAGE: Z - pointer to RAM buffer element Y - pointer to RAM buffer element i - index root - index helper  heapsize - index limit axl,bxl - bytes to compare@OUTPUT:RAM buffer sorted out!----------------------------------------------------------------------------*/Signed8bitHeapSortEx:  mov root,BUFFER_SIZE  lsr root   mov heapsize,BUFFER_SIZEsforloop: //BUILD MAX HEAP  mov i,root  rcall Signed8maxheapify  dec root  cpi root,1  brsh sforloop//heap sort  mov i,BUFFER_SIZE  mov root,BUFFER_SIZE  mov heapsize,BUFFER_SIZEsheapsortloop: //swap A[1] and A[i] ;first and last  ldi ZL,low(buffer) ldi ZH,high(buffer)  adiw ZH:ZL,1  ld ax,-Z  ldi YL,low(buffer)  ldi YH,high(buffer)  clr temp  ADD16 YL,YH,root,temp  ld bx,-Y  st Z,bx  st Y,ax	  //heap-size[A]=heap-size[A]-1  dec heapsize  ldi i,1  rcall Signed8maxheapify  dec root  cpi root,2  brsh sheapsortloop ret/******8 bit Signed Max Heapify****************Maintain max-heap property for signed 8 bit@INPUT heapsize - size of the sub-buffer to sort i - index into the array@USAGE: Z - pointer to RAM buffer element Y - pointer to RAM buffer element l - LEFT(i) r - RIGHT(i) temp,largest - temporary axl,bxl - bytes to compare@OUTPUT:Maintain heap property at A[i]*/Signed8maxheapify: ;check if lsl overflows the byte boundery  cpi i,0b10000000  brlo sboundary retsboundary:  mov l,i  lsl l  mov r,i  lsl r  inc r //if l<=heap_size[A]  cp heapsize,l  brlo smaxl   //A[l]  ldi ZL,low(buffer)  ldi ZH,high(buffer)  clr temp  ADD16 ZL,ZH,l,temp  ld ax,-Z //A[i]  ldi ZL,low(buffer)  ldi ZH,high(buffer)  clr temp  ADD16 ZL,ZH,i,temp  ld bx,-Z //if A[i]<A[l]  cp bx,ax  brge smaxl //signed   mov largest,l  rjmp smaxlon smaxl: //largest<-i  mov largest,ismaxlon: //do the same for the right  //if r<=heap_size[A]  cp heapsize,r  brlo smaxr //A[r]  ldi ZL,low(buffer)  ldi ZH,high(buffer)  clr temp  ADD16 ZL,ZH,r,temp  ld ax,-Z //A[largest]  ldi ZL,low(buffer)  ldi ZH,high(buffer)  clr temp  ADD16 ZL,ZH,largest,temp  ld bx,-Z //A[r]>A[largest]  cp bx,ax  brge smaxr //signed  mov largest,rsmaxr: //if largest!=i  cp largest,i  breq smaxend //swap  ldi ZL,low(buffer)  ldi ZH,high(buffer)  clr temp  ADD16 ZL,ZH,i,temp  ld ax,-Z  ldi YL,low(buffer)  ldi YH,high(buffer)  clr temp  ADD16 YL,YH,largest,temp  ld bx,-Y  st Z,bx  st Y,ax //prepare next iteration  mov i,largest  rjmp Signed8maxheapifysmaxend:ret`

Unsigned 16 bit heap sort

```/*
`/*------------------16 bit Signed Heap Sort----------------------------------@INPUT buffersize - 2 byte long number up to 2^16@USAGE: Z - pointer to RAM buffer element Y - pointer to RAM buffer element i - index root - index helper  heapsize - index limit a,b - number to compare@OUTPUT:RAM buffer sorted out!----------------------------------------------------------------------------*/Signed16bitHeapSortEx: //i=lenght[A]/2 mov rootl,buffersizel mov rooth,buffersizeh  LSR16 ih,il ;devide by 2 mov heapsizel,buffersizel mov heapsizeh,buffersizeh//hepifysforloop: mov il,rootl mov ih,rooth rcall Signed16maxheapify ADDI16 rootl,rooth,-1 ;decrement by 1 CPI16 rootl,rooth,temp,1 ;temp is temporary and destroyed brsh sforloop//heap sort ;mov il,buffersizel ;mov il,buffersizeh mov rootl,buffersizel mov rooth,buffersizeh mov heapsizel,buffersizel mov heapsizeh,buffersizehsheapsortloop: //swap A[1] and A[i] ;first and last ldi ZL,low(buffer16) ldi ZH,high(buffer16) adiw ZH:ZL,2 ;2 byte number ld ah,-Z ld al,-Z ldi YL,low(buffer16) ldi YH,high(buffer16) mov templ,rootl mov temph,rooth LSL16 temph,templ ADD16 YL,YH,templ,temph ld bh,-Y ld bl,-Y //swap st Z,bl std Z+1,bh st Y,al std Y+1,ah //heap-size[A]=heap-size[A]-1 ADDI16 heapsizel,heapsizeh,-1  ldi il,1 ldi ih,0 rcall Signed16maxheapify ADDI16 rootl,rooth,-1  CPI16 rootl,rooth,temp,2 brsh sheapsortloopret/******16 bit Signed Max Heapify****************Maintain max-heap property for signed 16 bit@INPUT heapsize - size of the sub-buffer to sort i - index into the array@USAGE: Z - pointer to RAM buffer element Y - pointer to RAM buffer element l - LEFT(i) r - RIGHT(i) temp,largest - temporary ax,bx - bytes to compare@OUTPUT:Maintain heap property at A[i]*/Signed16maxheapify:;check if lsl overflows the word boundery CPI16 il,ih,temp,32768 ;0x8000 brlo sboundary retsboundary: mov ll,il mov lh,ih LSL16 lh,ll ;LEFT index mov rl,il mov rh,ih LSL16 rh,rl ADDI16 rl,rh,1 ;RIGHT index   //if l<=heap_size[A] CP16 heapsizel,heapsizeh,ll,lh brlo smaxl //A[l] ldi ZL,low(buffer16) ldi ZH,high(buffer16) //dealing with 2 byte size number mov templ,ll mov temph,lh LSL16 temph,templ ADD16 ZL,ZH,templ,temph ld ah,-Z ld al,-Z  //A[i] ldi ZL,low(buffer16) ldi ZH,high(buffer16) mov templ,il mov temph,ih LSL16 temph,templ ADD16 ZL,ZH,templ,temph ld bh,-Z ld bl,-Z //if A[i]<A[l] CP16 bl,bh,al,ah brge smaxl //signed mov largestl,ll //largest<-l mov largesth,lh rjmp smaxlonsmaxl: //largest<-i mov largestl,il  mov largesth,ihsmaxlon: //do the same for the right  //if r<=heap_size[A] CP16 heapsizel,heapsizeh,rl,rh brlo smaxr //A[r] ldi ZL,low(buffer16) ldi ZH,high(buffer16) //dealing with 2 byte size number mov templ,rl mov temph,rh LSL16 temph,templ ADD16 ZL,ZH,templ,temph ld ah,-Z ld al,-Z //A[largest] ldi ZL,low(buffer16) ldi ZH,high(buffer16) mov templ,largestl mov temph,largesth LSL16 temph,templ ADD16 ZL,ZH,templ,temph ld bh,-Z ld bl,-Z //A[r]>A[largest] CP16 bl,bh,al,ah brge smaxr ;signed;largest<-r mov largestl,rl  mov largesth,rhsmaxr: //if largest!=i CP16 largestl,largesth,il,ih breq smaxend   //swap ldi ZL,low(buffer16) ldi ZH,high(buffer16) mov templ,il mov temph,ih LSL16 temph,templ ADD16 ZL,ZH,templ,temph ld ah,-Z ld al,-Z   ldi YL,low(buffer16) ldi YH,high(buffer16) mov templ,largestl mov temph,largesth LSL16 temph,templ ADD16 YL,YH,templ,temph ld bh,-Y ld bl,-Y st Z,bl std Z+1,bh st Y,al std Y+1,ah //prepare next iteration mov il,largestl mov ih,largesth rjmp Signed16maxheapify smaxend:ret`
`.MACRO CP16 cp @0,@2 ;Compare low byte cpc @1,@3 ;Compare high byte with carry from ;previous operation.ENDMACRO.MACRO ADDI16 subi @0,low(-@2) sbci @1,high(-@2).ENDMACRO.MACRO CPI16 cpi @0,low(@3) ;Compare low byte ldi @2,high(@3) ; cpc @1,@2 ;Compare high byte.ENDMACRO.MACRO ADD16  add @0,@2 ;Add low bytes adc @1,@3 ;Add high bytes with carry.ENDMACRO;@MACRO LSL16 MSB,LSB.MACRO LSL16 lsl @1 rol @0.ENDMACRO;@MACRO LSR16 MSB,LSB.MACRO LSR16 lsr @0 ror @1.ENDMACRO`