mrgsort2.cpp

经典c++程序的实现

// This is the "optimized" Mergesort without a cutoff threshold.
#include "..\include\book.h"

typedef int ELEM;
#include "..\include\swap.h"

extern long count1;

void mergesort(ELEM* array, ELEM* temp, int left, int right) {
  int i, j, k, mid = (left+right)/2;
  if (left == right) return;
  mergesort(array, temp, left, mid);    // Mergesort first half
  mergesort(array, temp, mid+1, right); // Mergesort second half

  // Do the merge operation.  First, copy 2 halves to temp.
  for (i=left; i<=mid; i++) temp[i] = array[i];
  for (j=1; j<=right-mid; j++) temp[right-j+1] = array[j+mid];
  // Merge sublists back to array
  for (i=left,j=right,k=left; k<=right; k++)
    if (temp[i] < temp[j]) array[k] = temp[i++];
    else array[k] = temp[j--];
}

void sort(ELEM* array, ELEM* tp, int listsize) {
  mergesort(array, tp, 0, listsize-1);
}