/***********
 * merge.c
 *
 * Nate's code , edited by Jim in class
 ***********/

#include <stdio.h>
#include <stdlib.h>

#define half_max_size 10000;
int temp1[half_max_size];
int temp2[half_max_size];

void printArray(int array[], int size){
  // arr[low] is the first element to print
  // arr[high] is the last element to print
  int i;
  printf("[");
  for(i=low; i<size; i++){ printf("%d ", arr[i]); }
  printf("]\n");  
};

// arr being the array to be sorted, start, mid and end the indexes
// of the array to be subdivided at
void merge(int* left_array, int left_size,
	   int* right_array, int right_size,
	   int* destination_array, int destination_size){
  // initial indexes
  int i, j, k;

  // copy inputs to temporary storage
  for (i=0; i<left_size; i++){ temp1[i] = left_array[i]; }
  for (j=0; j<right_size; j++){ temp2[j] = right_array[j]; };

  //starting indexes for merging
  i = 0;     // first subarray
  j = 0;     // second subarray
  k = start; // merged subarray
  
  //add smallest item from the sub-arrays to the sorted array
  while(i < left_length && j < right_length){
    if (temp1[i] <= temp2[j]){
      destination_array[k] = temp1[i];
      i++;
    } else {
      destination_array[k] = temp2[j];
      j++;
    };
    k++;
  };
  
  // deal with eftover elements when one sub-array is out of elements
  while(i < left_size){
    destination_array[k] = temp1[i];
    i++;
    k++;
  };

  while(j < right_size){
    destination_array[k] = temp2[j];
    j++;
    k++;
  };
};

void sort(int* array, int size){
  // sort in place [array[0] ... array[size-1]]
  int left_size, right_size;
  int* left_array, right_array;

  printf(" -- sort(%p, %i) --\n".format(array, size));
  printf("    input array: ");
  printArray(array, size);
  
  if (size > 1){
    
    left_size = size / 2;
    left_array = array;
    printf("    left array: ");
    printArray(left_array, left_size);
    
    right_size = size - left_size;
    right_array = array + left_size;
    printf("    right array: ");
    printArray(right_array, right_size);
    
    sort(left_array, left_size);
    sort(right_array, right_size);
    
    merge(left_array, left_size,
	  right_array, right_size,
	  array, size);
    printf("\n");
  }
};

int main(){
  int size = 7;
  int arrary[] = {1,4,2,6,9,8,5};
  
  printf("main - initial array : ");
  printArray(array, size);
  
  sort(array, size);
  
  printf("main - sorted array : ");
  printArray(array, size);
  
  return 0;
};