// Example: Mergesort

#include <iostream.h>
#include <assert.h>
#include <conio.h>

void merge(int *arr, int m, int n)      
{
   // Merge the two sorted "halves" in place
   // PRECONDITIONS:
   //    The first sorted "half" is in  arr[0] ,..., arr[m-1]
   //    The second sorted "half" is in arr[m] ,..., arr[n-1]
   //    Hence, n >= m.  
   // POSTCONDITIONS:
   //    The sorted "halves" have been merged into a sorted array
   //    stored in arr[0] ,..., arr[n-1].

  int *tmp = new int[n];    // Dynamically allocate temporary array for merge
  assert(tmp);  // checks that memory was available (see help on assert)
  int i=0,  // index into arr[0..m-1]
      j=m,  // index into arr[m..n-1]
      k=0;  // index into tmp[0..n-1]

  while ( ( i < m )  &&  ( j < n ) )   // Merge
    if ( arr[i] < arr[j] )
      tmp[k++] = arr[i++];
    else
      tmp[k++] = arr[j++];

  while ( i < m )          // Copy the rest of arr[0..m-1]
    tmp[k++] = arr[i++];            // -OR-

  while ( j < n )          // Copy the rest of arr[m..n-1]
    tmp[k++] = arr[j++];

  for (k=0; k<n; k++)      // Copy back from tmp to arr
    arr[k] = tmp[k];

  delete[] tmp;      // Deallocate dynamically-allocated array
}

void mergesort(int *arr, int n)    // Sort the n elements in array arr using
{                                  //  the recursive mergesort algorithm

  if ( n <= 1 )     // If there are fewer than two elements,
    return;         //  the array is already sorted

  int m = n/2;            // "Split" the array in half
  mergesort(arr, m);      // Sort the first half
  mergesort(arr+m, n-m);  // Sort the second half
  merge(arr, m, n);       // Merge the two sorted subarrays
}

void main(void)
{
  cout << "INTEGER SORTING PROGRAM\n";
  int n;
  cout << "Enter the number of integers to sort: ";
  cin >> n;
  int *nums = new int[n];   // dynamically allocate array of n ints
  assert(nums);             // check for success of new

  int i;
  for (i=0; i<n; i++)
  {
    cout << "Enter next integer: ";
    cin >> nums[i];
  }

  mergesort(nums, n);

  cout << "Here is your list, in sorted order: \n";
  for (i=0; i<n; i++)
    cout << nums[i] << endl;
  delete[] nums;            // deallocate dynamically-allocated array
  getch();
}