#include <iostream>
#include <cstdlib>
#include <iterator>
#include <algorithm>
using namespace std;

#if 0
void mysort(int *p, size_t n)
{
	while (--n >= 1) {

		//Examine and move elements 0 through n inclusive.
		//Always have n >= 1.
		for (size_t i = 0; i < n; ++i) {
			if (p[i + 1] < p[i]) {
				const int temp = p[i];   //swap them
				p[i] = p[i + 1];
				p[i + 1] = temp;
			}
		}
	}
}
#endif

#if 0
//Examine and move elements first through last inclusive.
//Assume have first < last.
void inner(int *p, size_t first, size_t last)
{
	if (p[first + 1] < p[first]) {
		const int temp = p[first];   //swap them
		p[first] = p[first + 1];
		p[first + 1] = temp;
	}

	if (first + 1 < last) {
		inner(p, first + 1, last);
	}
}

void outer(int *p, size_t n)
{
	if (n > 1) {
		inner(p, 0, n - 1);
		outer(p, n - 1);
	}
}
#endif

template <size_t FIRST, size_t LAST>
void inner(int *p)
{
	if (p[FIRST + 1] < p[FIRST]) {
		const int temp = p[FIRST];   //swap them
		p[FIRST] = p[FIRST + 1];
		p[FIRST + 1] = temp;
	}

	inner<
		FIRST + 1 >= LAST ? 0 : FIRST + 1,
		FIRST + 1 >= LAST ? 0 : LAST
	>(p);
}

template <size_t N>
void outer(int *p)
{
	inner<0, N - 1>(p);
	outer<N - 1>(p);
}

template <> void inner<0, 0>(int *p) {}
template <> void outer<1>   (int *p) {}

int main()
{
	int a[] = {50, 20, 30, 10, 40};
	const size_t n = sizeof a / sizeof a[0];
	outer<n>(a);
	copy(a, a + n, ostream_iterator<int>(cout, "\n"));

	return EXIT_SUCCESS;
}