hw6/mergesort.cpp at master · derwolfe/hw6 · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
using namespace std;
#include <string>

#include "data_type.h"
#include "utility.h"


const int MAX_SIZE = 100000;

/** Merges two sorted array segments theArray[first..mid] and
 *  theArray[mid+1..last] into one sorted array.
 *
 * Precondition:  first <= mid <= last. The subarrays theArray[first..mid]
 * and theArray[mid+1..last] are each sorted in increasing order.
 *
 * Postcondition: theArray[first..last] is sorted.
 *
 * Parameter: theArray - The given array.
 * Parameter: first    - The beginning of the first segment in theArray.
 * Parameter: mid      - The end of the first segement in theArray.
 *                       mid + 1 marks the beginning of the second segment.
 * Parameter: last     - The last element in the second segment in theArray.
 *
 * Note: This function merges the two subarrays into a temporary array
 * and copies the result into the original array theArray.
 */
void merge(DataType theArray[],
           int first, int mid, int last)
{
  DataType tempArray[MAX_SIZE];    /* temporary array */

  /*
   * initialize the local indexes to indicate the subarrays
   */
  int first1 = first;   /* beginning of first subarray*/
  int last1  = mid;     /* end of first subarray*/
  int first2 = mid + 1; /* beginning of second subarray */
  int last2  = last;    /* end of second subarray */

  int index = first1;   /* next available location in tempArray */

  /*
   * while both subarrays are not empty, copy the
   * smaller item into the temporary array
   */
   for (; (first1 <= last1) && (first2 <= last2); ++index) {
     /*
      * Invariant: tempArray[first..index-1] is in order
      */
     if (theArray[first1] < theArray[first2]) {
	tempArray[index] = theArray[first1];
         ++first1;
      } else {
	tempArray[index] = theArray[first2];
	++first2;
      }
   }

   /*
    * finish off the nonempty subarray
    * finish off the first subarray, if necessary
    */
   for (; first1 <= last1; ++first1, ++index)
     /*
      * Invariant: tempArray[first..index-1] is in order
      */
     tempArray[index] = theArray[first1];

   /*
    * finish off the second subarray, if necessary
    */
   for (; first2 <= last2; ++first2, ++index)
     /*
      * Invariant: tempArray[first..index-1] is in order
      */
     tempArray[index] = theArray[first2];

   /*
    * copy the result back into the original array
    */
   for (index = first; index <= last; ++index)
      theArray[index] = tempArray[index];
}

/** Sorts the items in an array into ascending order.
 * Precondition: theArray[first..last] is an array.
 * Postcondition:  theArray[first..last] is sorted in ascending order.
 * Parameter:  theArray  The given array.
 * Parameter:  first  The first element to consider in theArray.
 * Parameter:  last  The last element to consider in theArray. */
void mergesort(DataType theArray[], int first, int last)
{
  if (first < last) {
    /*
     * sort each half
     */
    int mid = (first + last)/2;    /* index of midpoint */
    /*
     * sort left half theArray[first..mid]
     */
    mergesort(theArray, first, mid);
    /*
     * sort right half theArray[mid+1..last]
     */
    mergesort(theArray, mid+1, last);

    /*
     * merge the two halves
     */
    merge(theArray, first, mid, last);
  }
}