#include <stdio.h>
#include <math.h>
#include "mergesort.h"

void quicksort(float *data, int begin, int end)
{
  /***********************************************************************/
  /* Purpose: sorts a list of numbers in increasing order                */
  /* Input:                                                              */
  /*   data: an unsorted array of numbers                                */
  /*   begin: the beginning index of "data"                              */
  /*   end: the final index of "data"                                    */
  /* Output:                                                             */
  /*   upon termination of the subroutine, "data" contains the sorted    */
  /*     list of numbers                                                 */
  /***********************************************************************/

  int leftarrow, rightarrow;
  float temp, pivot;

  leftarrow = begin;
  rightarrow = end;
  pivot = data[(begin+end)/2];
  while (1)
  {
    while (data[rightarrow] > pivot)
      rightarrow = rightarrow - 1;

    while (data[leftarrow] < pivot)
      leftarrow = leftarrow + 1;

    if (leftarrow <= rightarrow)
    {
      temp = data[leftarrow];
      data[leftarrow] = data[rightarrow];
      data[rightarrow] = temp;
      leftarrow = leftarrow + 1;
      rightarrow = rightarrow - 1;
    }

    if (rightarrow < leftarrow)
      break;
  } 

  if (begin < rightarrow)
    quicksort(data,begin,rightarrow);
  if (leftarrow < end)
    quicksort(data,leftarrow,end);

  return;
}

void merge(float *data1, int length1, float *data2, int length2,
  float *newlist)
{
  /***********************************************************************/
  /* Purpose: merges two sorted sublists (in increasing order) to form   */
  /*   a single sorted list                                              */
  /* Input:                                                              */
  /*   data1: a sorted array of numbers                                  */
  /*   length1: the length of array data1                                */
  /*   data2: a second sorted array of numbers                           */
  /*   length2: the length of array data2                                */
  /* Output:                                                             */
  /*   upon termination of the subroutine, "newlist" contains the        */
  /*     merged list of numbers, sorted in increasing order              */
  /***********************************************************************/

  int leftarrow1, rightarrow1, leftarrow2, rightarrow2, i;

  /* initialize variables */
  leftarrow1 = 0;
  rightarrow1 = length1-1;
  leftarrow2 = 0;
  rightarrow2 = length2-1;
  i=0;
  
  /* while both arrays are nonempty, copy the smallest element 
     appearing in either array, into newlist */
  while ((leftarrow1 <= rightarrow1) && (leftarrow2 <= rightarrow2))
  {
    if (data1[leftarrow1] < data2[leftarrow2])
    {
      newlist[i] = data1[leftarrow1];
      leftarrow1++;
    }
    else
    {
      newlist[i] = data2[leftarrow2];
      leftarrow2++;
    }
    i++;
  }
 
  /* finish nonempty array data1, if necessary */
  while (leftarrow1 <= rightarrow1)
  {
    newlist[i] = data1[leftarrow1];
    leftarrow1++;
    i++;
  }

  /* finish nonempty array data2, if necessary */
  while (leftarrow2 <= rightarrow2)
  {
    newlist[i] = data2[leftarrow2];
    leftarrow2++;
    i++;
  }

  return;
}