mrgsort3.cpp

经典c++程序的实现

// This is the "optimized" Mergesort that uses selection sort to make
// the small sublists.
#include "..\include\book.h"

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

extern long count1;
extern long count2;
extern int THRESHOLD;

void selsort(ELEM* array, int n) { // Selection Sort
  for (int i=0; i<n-1; i++) {      // Select i'th record
    int lowindex = i;              // Remember its index
    for (int j=n-1; j>i; j--)      // Find the least value
      if (key(array[j]) < key(array[lowindex]))
	lowindex = j;              // Put it in place
    swap(array[i], array[lowindex]);
  }
}

void mergesort(ELEM* array, ELEM* temp, int left, int right) {
  int i, j, k, mid = (left+right)/2;
  if (left == right) return;
  if ((mid-left)<THRESHOLD)
    { count2++; selsort(&array[left], mid-left); }
  else mergesort(array, temp, left, mid);  // Mergesort first half
  if ((right-mid-1)<THRESHOLD)
    {count2++; selsort(&array[mid+1], right-mid-1); }
  else mergesort(array, temp, mid+1, right);  // Mergesort second half
  // Do the merge operation.  First, copy 2 halves to temp.
  for (i=mid; i>=left; 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);
}