MergeSort

Here is a complete MergeSort that uses the Merger and Sorter processor objects discussed in this chapter. This pobj_MergeSort.cc++ creates 2 sorters and 1 merger, splitting the work evenly between the sorters.


#include "pobj_MergeSort.h"
#include <iostream.h>
#include <stdlib.h>

int read_output (DList_removing* out, int N)
{
  int prev = -1;
  int all_correct = 1;
  for (int i=0; i<N; i++)  {
    int temp = out->remove();
    if (temp<prev)  { 
      cout << "GOT ITEM #"<<i<<" OUT OF ORDER" << endl; 
      all_correct = 0; 
    }
    prev = temp;
  }
  out->remove(); // ENDVALUE
  return all_correct;
}

int main (int argc, char* argv[])
{
  if (argc<5)  {
    cout << "MergeSort::Not enough arguments.  Expect:" << endl;
    cout << "  Argument 1) # of Elements to sort (N)" << endl;
    cout << "  Argument 2) Machine to place merger" << endl;
    cout << "  Arguments 3,4) Machines to place sorters" << endl;
    exit(1);
  }
  int N = atoi(argv[1]);
  proc_t merger_placement("pobj_Merger.out",argv[2]);
  proc_t sorter0_placement("pobj_Sorter.out",argv[3]);
  proc_t sorter1_placement("pobj_Sorter.out",argv[4]);

  Sorter *global sorters[2];
  Merger *global merger;

  // Create Merger Processor Object
  DList_removing* final_output = new DList_removing();
  merger = new (merger_placement) Merger(final_output);

  // Create Sorter Processor Objects
  DList_removing* global merger_left_input = merger->get_in1();
  sorters[0] = new (sorter0_placement) Sorter(merger_left_input,0,N/2);

  DList_removing* global merger_right_input = merger->get_in2();
  sorters[1] = new (sorter1_placement) Sorter(merger_right_input,N/2,N);

  // Check that output list is in ascending order
  int result = read_output(final_output,N);
  if (result==0)  cout << "Incorrect MergeSort" << endl;
    else          cout << "Correct MergeSort" << endl;

  // Deallocate Processor Objects
  delete merger; delete sorters[0]; delete sorters[1];
  return result;
}

To compile and run this, we write


>cc++ pobj_MergeSort.cc++ -o pobj_MergeSort.out gptr_dlist.o
>pvmd hostfile &
>pobj_MergeSort.out 100 fides hebe rhea

paolo@cs.caltech.edu