1: // Created by Frank M. Carrano and Tim Henry.
2: // Copyright (c) 2013 __Pearson Education__. All rights reserved.
4: // Listing 11-4.
6: #include <iostream>
7: #include <string>
9: using namespace std;
11: const int MAX_SIZE = 50;
13: template<class ItemType>
15: /** Merges two sorted array segments theArray[first..mid] and
16: theArray[mid+1..last] into one sorted array.
17: @pre first <= mid <= last. The subarrays theArray[first..mid] and
18: theArray[mid+1..last] are each sorted in increasing order.
19: @post theArray[first..last] is sorted.
20: @param theArray The given array.
21: @param first The index of the beginning of the first segment in theArray.
22: @param mid The index of the end of the first segment in theArray;
23: mid + 1 marks the beginning of the second segment.
24: @param last The index of the last element in the second segment in theArray.
25: @note This function merges the two subarrays into a temporary
26: array and copies the result into the original array theArray. */
27: void merge(ItemType theArray[], int first, int mid, int last)
28: {
29: ItemType tempArray[MAX_SIZE]; // Temporary array
30:
31: // Initialize the local indices to indicate the subarrays
32: int first1 = first; // Beginning of first subarray
33: int last1 = mid; // End of first subarray
34: int first2 = mid + 1; // Beginning of second subarray
35: int last2 = last; // End of second subarray
36:
37: // While both subarrays are not empty, copy the
38: // smaller item into the temporary array
39: int index = first1; // Next available location in tempArray
40: while ((first1 <= last1) && (first2 <= last2))
41: {
42: // At this point, tempArray[first..index-1] is in order
43: if (theArray[first1] <= theArray[first2])
44: {
45: tempArray[index] = theArray[first1];
46: first1++;
47: }
48: else
49: {
50: tempArray[index] = theArray[first2];
51: first2++;
52: } // end if
53: index++;
54: } // end while
55:
56: // Finish off the first subarray, if necessary
57: while (first1 <= last1)
58: {
59: // At this point, tempArray[first..index-1] is in order
60: tempArray[index] = theArray[first1];
61: first1++;
62: index++;
63: } // end while
64:
65: // Finish off the second subarray, if necessary
66: while (first2 <= last2)
67: {
68: // At this point, tempArray[first..index-1] is in order
69: tempArray[index] = theArray[first2];
70: first2++;
71: index++;
72: } // end for
73:
74: // Copy the result back into the original array
75: for (index = first; index <= last; index++)
76: theArray[index] = tempArray[index];
77: } // end merge
79: /** Sorts the items in an array into ascending order.
80: @pre theArray[first..last] is an array.
81: @post theArray[first..last] is sorted in ascending order.
82: @param theArray The given array.
83: @param first The index of the first element to consider in theArray.
84: @param last The index of the last element to consider in theArray. */
85: void mergeSort(ItemType theArray[], int first, int last)
86: {
87: if (first < last)
88: {
89: // Sort each half
90: int mid = first + (last - first) / 2; // Index of midpoint
91:
92: // Sort left half theArray[first..mid]
93: mergeSort(theArray, first, mid);
94:
95: // Sort right half theArray[mid+1..last]
96: mergeSort(theArray, mid + 1, last);
97:
98: // Merge the two halves
99: merge(theArray, first, mid, last);
100: } // end if
101: } // end mergeSort
103: int main()
104: {
105: string a[6] = {"Z", "X", "R", "K", "F", "B"};
106: mergeSort(a, 0, 5);
107: for (int i = 0; i < 6; i++)
108: cout << a[i] << " ";
109: cout << endl;
110:
111: } // end main
113: /*
115: B F K R X Z
116:
117: */