#include <bassert.h>
#include <mem_syms.h>

int * merge(int *list1, int len1, int *list2, int len2) {

/* 
Pre: list list1 of length len1, list list2 of length len2 
     both sorted in ascending order.

Post: returns a pointer to a list (on heap) of length 
     len1+len2 in increasing order resulting from the ordered
     merge of len1 and len2

Invariant: list list1 and list2 are not modified.

Problem: who is responsible for freeing the merged list later when it is
not needed?
*/


  int lenr = len1 + len2;
  int *result;
  int next1 = 0;    // index of next element to take from from list 1
  int next2 = 0;    // index of next element to take from from list 1
  int nextr = 0;    // index of next element to insert into the result list
  
  bassert( len1 > 0 || len2 > 0, 2);

  result = (int *) malloc( lenr * sizeof(int));
  bassert(result != 0, 5);

  while ( len1 + len2 > 0 ) {
    // select smaller of next element of list1 or list2 if there is one

      
    byte take_from_1 = 
        (len2 == 0) || (len1 > 0 && list1[next1] <= list2[next2]);
       
       if ( take_from_1 ) {
         result[nextr] = list1[next1];
         len1--; 
         next1++;
       } else {
         result[nextr] = list2[next2];
         len2--; 
         next2++;
       }
       nextr++;
    
  }
  return result; 

}

int * mergesort(int *l, int len) {
/*

Pre: l is a list of len elements.

Post: returns a pointer to a new list of len elements that is l sorted in
    ascending order.

Invariant: list l is not modified.

Problem: Since we never free the intermediate storage we use for 
  the recursion we get a memory leak.  Also, how much storage do we 
  allocate?  Each level of the recursion allocates n (across the
  width of the recursion) so we allocate an extra O(n log n) of space.
*/

  // split the list roughly in half
  if ( len <= 1 ) { return l; }
  int len1 = len / 2;
  return merge(
        mergesort(l, len1), len1,
        mergesort(l+len1, len-len1), len-len1);
}


void setup() {
  Serial.begin(9600);
  
  int len = 32;
  int l[32];
  int *r;
  
  for (int i=0; i < len; i++ ) { l[i] = random(100); }
  
  Serial.println("In:");
  for (int i=0; i < len; i++ ) { 
    Serial.print(l[i]); Serial.print(" "); 
  }
  Serial.println("");

  Serial.println("Out:");
  r = mergesort(l, len);
  for (int i=0; i < len; i++ ) { 
    Serial.print(r[i]); Serial.print(" "); 
  }

}

void loop() {
}