/**********************************************************************
 * mergesort.cc
 * Tom Kelliher
 *
 * Demonstrates the mergesort algorithm
 **********************************************************************/


#include <iostream.h>
#include <stdlib.h>
#include <time.h>
#include <assert.h>


const int DATA_SIZE = 20;   // Number of ints to sort.


// Prototypes.
void mergesort(int *, int);
void merge(int *, int);
void move(int *, int *, int);


/**********************************************************************
 * main
 **********************************************************************/

int main() {

    int data[DATA_SIZE];   // Storage for int to be sorted.
    int *intptr,           // "Index" pointer.

    // Seed the random number generator.
    srand((unsigned) time((time_t *) NULL));

    cout << "\nUnsorted list:\n\n";

    // Get random numbers for the unsorted data.
    for (intptr = data; intptr < data + DATA_SIZE; intptr++)
       cout << (*intptr = rand()) << endl;

    mergesort(data, DATA_SIZE);

    cout << "\nSorted list:\n\n";

    for (intptr = data; intptr < data + DATA_SIZE; intptr++)
       cout << *intptr << endl;

    return (0);
}


/**********************************************************************
 * mergesort
 *
 * data is the address of the first element to be sorted.
 * len is the number of elements to sort.
 **********************************************************************/

void mergesort(int *data, int len) {

    int half = len / 2;

    if (len < 2)
      return;

    mergesort(data, half);   // Sort first half of data.
    mergesort(data + half, len - half);   // Sort second half of data.

    // Merge two sorted halves into a sorted whole.
    merge(data, len);
}


/**********************************************************************
 * merge
 *
 * data is the address of the first element to be merged.
 * len is the number of elements in BOTH halves to be merged.
 **********************************************************************/

void merge(int *data, int len) {

    int half = len / 2;
    int *p1 = data;   // Pointer to elements in first half.
    int *p2 = data + half;   // Pointer to elements in second half.
    int *ary, *ap;   // Pointers for temporary array.

    // The merged whole is temporarily stored here.
    assert ((ap = ary = new int[len]) != NULL);

    // While neither half is exhausted, look at smallest element in
    // each half, moving the smaller into the temporary array.
    while (p1 < data + half && p2 < data + len)
      if (*p1 < *p2)
        *ap++ = *p1++;
      else
        *ap++ = *p2++;

    // Still a few elements left in first half, move them over to the
    // temporary array.
    if (p1 < data + half)
      move(ap, p1, data + half - p1);
    else   // Elements left in the second half.  Move them.
      move(ap, p2, data + len - p2);

    // Move elements from the temporary array back to the original array.
    move(data, ary, len);


    delete [] ary;   // Discard the temporary array.
}


/**********************************************************************
 * move
 *
 * Move len ints from source to target.
 **********************************************************************/

void move(int *target, int *source, int len) {

    int i;

    for (i = 0; i < len; i++)
      *target++ = *source++;
}