Merge Sort Iterative Version

merge_sort_iterative.cpp

#include <iostream>
#include <vector>
#include <limits>

using namespace std;

void merge(vector<int> & data, int p, int q, int r) {
	// merge data[p..q] and data[q+1..r]
	int n1 = q - p + 1;
	int n2 = r - q;

	vector<int> A, B;
	A.resize(n1);
	B.resize(n2);
	for (int i = 0; i < n1; i++)
		A[i] = data[p+i];
	for (int i = 0; i < n2; i++)
		B[i] = data[q+i+1];

	int i = 0, j = 0;
	for (int k = p; k <= r; k++) {
		if (A[i] < B[j]) {
			data[k] = A[i];
			i++;
			if (i == n1) {
				for (k++; k <= r; k++)
					data[k] = B[j++];
				return;
			}
		} else {
			data[k] = B[j];
			j++;
			if (j == n2) {
				for (k++; k <= r; k++)
					data[k] = A[i++];
				return;
			}
		}
	}
}

void merge_sort(vector<int> & data, int p, int r) {
	int k = 1;
	while (p + 2 * k - 1 <= r) {
		for (int i = 1; p + 2 * k * i - 1 <= r; i++)
			merge(data, p + 2 * k * (i - 1), p + 2 * k * (i - 1) + k - 1, p + 2 * k * i - 1);
		k *= 2;
	}
	switch ((r - p + 1) % 4) {
	case 1:
		merge(data, p, r - 1, r);
		break;
	case 2:
		merge(data, p, r - 2, r);
		break;
	case 3:
		merge(data, p, r - 3, r - 1);
		merge(data, p, r - 1, r);
		break;
	default:
		return;
	}
}

int main () {
	vector<int> data {31, 41, 59, 26, 41, 58, 12};
	merge_sort(data, 0, data.size()-1);
	for (auto d : data)
		cout << d << " ";
	cout << endl;
}