In C++, do an iterative (non-recursive) merge sort using one additional array as
ID: 3831314 • Letter: I
Question
In C++, do an iterative (non-recursive) merge sort using one additional array as a semi in-place method. Merge data from the original into the additional array at the very bottom stage, and thereafter perform the next merge from the additional into the original array, in which way merge operations are applied to the original and additional array in turn as you go through each repetitive stage. Example: at the first merge, data is from original to additional array, and the next merge, data is from additional to original array.
The function at the bottom is to start out with.
Explanation / Answer
template <class Comparable> void merge(vector<Comparable> &a, vector<Comparable> &b, int &start, int &mid, int &end) { if (mid > end) return; int first1 = start; int last1 = mid; int first2 = mid + 1; int last2 = end; int index = first1; while ((first1 <= last1) && (first2 <= last2)) { if (a[first1] <= a[first2]) { b[index] = a[first1]; first1++; } else { b[index] = a[first2]; first2++; } index++; } while (first1 <= last1) { b[index] = a[first1]; first1++; index++; } while (first2 <= last2) { b[index] = a[first2]; first2++; index++; } for (index = start; index <= end; index++) { a[index] = b[index]; } } template <class Comparable> void mergesortImproved(vector<Comparable> &a) { int size = a.size(); vector<Comparable> b(size); int sizeSubArr; int start; for (sizeSubArr = 1; sizeSubArr < size; sizeSubArr *= 2) { for (start = 0; start < size - 1; start += (2 * sizeSubArr)) { int mid = start + sizeSubArr - 1; int end = findMin((start + (2 * sizeSubArr) - 1), size - 1); merge(a, b, start, mid, end); } } } int main() { vector<int> a; a.push_back(5); a.push_back(11); a.push_back(4); a.push_back(1); a.push_back(13); a.push_back(32); a.push_back(4); a.push_back(1); a.push_back(6); a.push_back(5); a.push_back(32); cout << "unsorted: " << endl; for (int i = 0; i < a.size(); i++) { cout << a[i] << endl; } mergesortImproved(a); cout << "sorted: " << endl; for (int i = 0; i < a.size(); i++) { cout << a[i] << endl; } return 0; }
template <class Comparable> void merge(vector<Comparable> &a, vector<Comparable> &b, int &start, int &mid, int &end) { if (mid > end) return; int first1 = start; int last1 = mid; int first2 = mid + 1; int last2 = end; int index = first1; while ((first1 <= last1) && (first2 <= last2)) { if (a[first1] <= a[first2]) { b[index] = a[first1]; first1++; } else { b[index] = a[first2]; first2++; } index++; } while (first1 <= last1) { b[index] = a[first1]; first1++; index++; } while (first2 <= last2) { b[index] = a[first2]; first2++; index++; } for (index = start; index <= end; index++) { a[index] = b[index]; } } template <class Comparable> void mergesortImproved(vector<Comparable> &a) { int size = a.size(); vector<Comparable> b(size); int sizeSubArr; int start; for (sizeSubArr = 1; sizeSubArr < size; sizeSubArr *= 2) { for (start = 0; start < size - 1; start += (2 * sizeSubArr)) { int mid = start + sizeSubArr - 1; int end = findMin((start + (2 * sizeSubArr) - 1), size - 1); merge(a, b, start, mid, end); } } } int main() { vector<int> a; a.push_back(5); a.push_back(11); a.push_back(4); a.push_back(1); a.push_back(13); a.push_back(32); a.push_back(4); a.push_back(1); a.push_back(6); a.push_back(5); a.push_back(32); cout << "unsorted: " << endl; for (int i = 0; i < a.size(); i++) { cout << a[i] << endl; } mergesortImproved(a); cout << "sorted: " << endl; for (int i = 0; i < a.size(); i++) { cout << a[i] << endl; } return 0; }