mrgsort1.cpp

来自「经典c++程序的实现」· C++ 代码 · 共 33 行

// This is the "simple" Mergesort.
#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 mid = (left+right)/2;
  if (left == right) return;            // List of one element
  mergesort(array, temp, left, mid);    // Mergesort first half
  mergesort(array, temp, mid+1, right); // Mergesort second half
  for (int i=left; i<=right; i++)       // Copy subarray to temp
    temp[i] = array[i];
  // Do the merge operation back to array
  int i1 = left; int i2 = mid + 1;
  for (int curr=left; curr<=right; curr++) {
    if (i1 == mid+1)      // Left sublist exhausted
      array[curr] = temp[i2++];
    else if (i2 > right)  // Right sublist exhausted
      array[curr] = temp[i1++];
    else if (temp[i1] < temp[i2])
      array[curr] = temp[i1++];
    else array[curr] = temp[i2++];
  }
}

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