1: // Created by Frank M. Carrano and Timothy M. Henry.
2: // Copyright (c) 2017 Pearson Education, Hoboken, New Jersey.
4: // Listing 11-4.
6: const int MAX_SIZE = 50;
7: /** Merges two sorted array segments theArray[first..mid] and
8: theArray[mid+1..last] into one sorted array.
9: @pre first <= mid <= last. The subarrays theArray[first..mid] and
10: theArray[mid+1..last] are each sorted in increasing order.
11: @post theArray[first..last] is sorted.
12: @param theArray The given array.
13: @param first The index of the beginning of the first segment in
14: theArray.
15: @param mid The index of the end of the first segment in theArray;
16: mid + 1 marks the beginning of the second segment.
17: @param last The index of the last element in the second segment in
18: theArray.
19: @note This function merges the two subarrays into a temporary
20: array and copies the result into the original array theArray. */
21: template <class ItemType>
22: void merge(ItemType theArray[], int first, int mid, int last)
23: {
24: ItemType tempArray[MAX_SIZE]; // Temporary array
25: // Initialize the local indices to indicate the subarrays
26: int first1 = first; // Beginning of first subarray
27: int last1 = mid; // End of first subarray
28: int first2 = mid + 1; // Beginning of second subarray
29: int last2 = last; // End of second subarray
30:
31: // While both subarrays are not empty, copy the
32: // smaller item into the temporary array
33: int index = first1; // Next available location in tempArray
34: while ((first1 <= last1) && (first2 <= last2))
35: {
36: // At this point, tempArray[first..index–1] is in order
37: if (theArray[first1] <= theArray[first2])
38: {
39: tempArray[index] = theArray[first1];
40: first1++;
41: }
42: else
43: {
44: tempArray[index] = theArray[first2];
45: first2++;
46: } // end if
47:
48: index++;
49: } // end while
50:
51: // Finish off the first subarray, if necessary
52: while (first1 <= last1)
53: {
54: // At this point, tempArray[first..index–1] is in order
55: tempArray[index] = theArray[first1];
56: first1++;
57: index++;
58: } // end while
59:
60: // Finish off the second subarray, if necessary
61: while (first2 <= last2)
62: {
63: // At this point, tempArray[first..index–1] is in order
64: tempArray[index] = theArray[first2];
65: first2++;
66: index++;
67: } // end for
68:
69: // Copy the result back into the original array
70: for (index = first; index <= last; index++)
71: theArray[index] = tempArray[index];
72: } // end merge
74: /** Sorts the items in an array into ascending order.
75: @pre theArray[first..last] is an array.
76: @post theArray[first..last] is sorted in ascending order.
77: @param theArray The given array.
78: @param first The index of the first element to consider in theArray.
79: @param last The index of the last element to consider in theArray. */
80: template<class ItemType>
81: void mergeSort(ItemType theArray[], int first, int last)
82: {
83: if (first < last)
84: {
85: // Sort each half
86: int mid = first + (last – first) / 2; // Index of midpoint
87:
88: // Sort left half theArray[first..mid]
89: mergeSort(theArray, first, mid);
90:
91: // Sort right half theArray[mid+1..last]
92: mergeSort(theArray, mid + 1, last);
93:
94: // Merge the two halves
95: merge(theArray, first, mid, last);
96: } // end if
97: } // end mergeSort