C / C++ / MFC

#include "stdafx.h"<br />
<br />
typedef int DataType;<br />
<br />
const int MAX_SIZE = 50;<br />
<br />
void merge(DataType theArray[], int first, int mid, int last);<br />
void mergesort(DataType theArray[], int first, int last)<br />
<br />
int _tmain(int argc, _TCHAR* argv[])<br />
{<br />
	int arrayToSend[4] = { 1, 2, 4, 3 };<br />
	mergesort( arrayToSend, 0, 3 );<br />
	return 0;<br />
}<br />
<br />
void merge(DataType theArray[], int first, int mid, int last)<br />
{<br />
   DataType tempArray[MAX_SIZE];    // temporary array<br />
<br />
   // initialize the local indexes to indicate the subarrays<br />
   int first1 = first;       // beginning of first subarray<br />
   int last1  = mid;         // end of first subarray<br />
   int first2 = mid + 1;     // beginning of second subarray<br />
   int last2  = last;        // end of second subarray<br />
<br />
   // while both subarrays are not empty, copy the<br />
   // smaller item into the temporary array<br />
   int index = first1;    // next available location in <br />
                          // tempArray<br />
   for (; (first1 <= last1) && (first2 <= last2); ++index)<br />
   {  // Invariant: tempArray[first1..index-1] is in order<br />
      if (theArray[first1] < theArray[first2])<br />
      {  tempArray[index] = theArray[first1];<br />
         ++first1;<br />
      }<br />
      else<br />
      {  tempArray[index] = theArray[first2];<br />
         ++first2;<br />
      }  // end if<br />
   }  // end for<br />
<br />
   // finish off the nonempty subarray<br />
<br />
   // finish off the first subarray, if necessary<br />
   for (; first1 <= last1; ++first1, ++index)<br />
      // Invariant: tempArray[first1..index-1] is in order<br />
      tempArray[index] = theArray[first1];<br />
<br />
   // finish off the second subarray, if necessary<br />
   for (; first2 <= last2; ++first2, ++index)<br />
      // Invariant: tempArray[first1..index-1] is in order<br />
      tempArray[index] = theArray[first2];<br />
<br />
   // copy the result back into the original array<br />
   for (index = first; index <= last; ++index)<br />
      theArray[index] = tempArray[index];<br />
}  // end merge<br />
<br />
void mergesort(DataType theArray[], int first, int last)<br />
{<br />
   if (first < last)<br />
   {  // sort each half<br />
      int mid = (first + last)/2;    // index of midpoint<br />
      // sort left half theArray[first..mid]<br />
      mergesort(theArray, first, mid);<br />
      // sort right half theArray[mid+1..last]<br />
      mergesort(theArray, mid+1, last);<br />
<br />
      // merge the two halves<br />
      merge(theArray, first, mid, last);<br />
   }  // end if<br />
}  // end mergesort