mergesort.c--

c--词法分析

/*
 * mergesort.c--
 * Written by Alex Benn
 * Last modified: 2007-04-24
 *
 * Mergesort algorithm implemented in C--. Written for the purposes of testing
 * our C-- compiler.
 */

int mergeSort(int arr[], int size) {
  if (size > 20) {
    return -1;
  } else {
    return merge(arr, 0, size);
  }
}

int merge(int a[], int start, int end) {
  int i;
  int n;
  int midpoint;
  int left;
  int right;
  int tmp[20];

  n = end - start;
  if (n <= 1) {
    return 0;
  } else {
    midpoint = start + n/2;
    merge(a, start, midpoint);
    merge(a, midpoint, end);
    
    i = start;
    while (i < end) {
      tmp[i] = a[i];
      i = i+1;
    }
    
    left = start;
    right = midpoint;
    i = start;
    while (i < end) {
      if (left < midpoint) {
	if (right < end) {
	  if (tmp[left] < tmp[right]) {
	    //pick lefthand side
	    a[i] = tmp[left];
	    left = left+1;
	  } else {
	    //pick righthand side
	    a[i] = tmp[right];
	    right = right+1;
	  }
	} else {
	  //right array is exhausted; pick from left
	  a[i] = tmp[left];
	  left = left+1;
	}
      } else {
	//left array is exhausted; pick from right
	a[i] = tmp[right];
	right = right+1;
      }
      i = i+1;
    }
    
    return 0;
  }
}

int printArray(int arr[], int size) {
  int i;

  i=0;
  while (i < size) {
    write arr[i];
    writeln;
    i = i+1;
  }
  return 0;
}

int main() {
  int array[10];

  array[0] = 16;
  array[1] = -5;
  array[2] = -1;
  array[3] = 12;
  array[4] = 9;
  array[5] = 1;
  array[6] = 18;
  array[7] = -32;
  array[8] = -1;
  array[9] = 0;


  printArray(array, 10);
  writeln;
  mergeSort(array, 10);
  printArray(array, 10);

  return 0;
}