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

class Sort
{
private:
	int *p;
	int len;

	void merge(int *a, int *b, int l1, int l2)
	{
		int i, j, t;
		int *q = new int[l1 + l2];

		for (i = j = t = 0 ; i < l1 && j < l2 ; )
		{
			if (a[i] > b[j])
				q[t++] = b[j++];
			else if (a[i] < b[j])
				q[t++] = a[i++];
			else
				q[t++] = a[i++], q[t++] = b[j++];
		}

		if (i == l1)
		{
			while (j < l2) q[t++] = b[j++];
		}
		else
		{
			while (i < l1) q[t++] = a[i++];
		}

		for (i = 0 ; i < l1 + l2 ; i++)
			a[i] = q[i];

		delete[] q;
	}
public:
	Sort (int n)
	{
		p = new int[n];

		len = n;

		for (int i = 0 ; i < n ; i++)
			p[i] = rand() % 1000;
	}

	bool init(void)
	{
		for (int i = 0 ; i < len ; i++)
			p[i] = rand() % 1000;
		return true;
	}

	~Sort ()
	{
		delete p;
	}

	bool insertion_sort(void)
	{
		for (int j = 1 ; j < len ; j++)
		{
			int key = p[j];
			int i = j - 1;
			while (i && p[i] > key)
			{
				p[i + 1] = p[i];
				i--;
			}
			p[i+1] = key;
		}
		return true;
	}

	bool selection_sort(void)
	{
		int i, j, m;
		for (i = 0 ; i < len ; i++)
		{
			for (m = i, j = i + 1 ; j < len ; j++)
			{
				if (p[j] > p[m])
					m = j;
			}
			int tmp = p[m];
			p[m] = p[i];
			p[i] = tmp;
		}
		return true;
	}

	bool merge_sort(void)
	{
		int i, j;
		for (i = 1 ; i < len ; i *= 2)
		{
			for (j = 0 ; j < len ; j += 2 * i)
				merge(p + j, p + j + i, i, len - j - i > i ? i : len - j - i);
		}

		return true;
	}

	bool display(void)
	{
		for (int i = 0 ; i < len ; i++)
			cout << p[i] << ' ';
		cout << endl;

		return true;
	}
};

int main(void)
{
	Sort s(20);

	s.display();
	s.insertion_sort();
	s.display();
	s.selection_sort();
	s.display();
	s.merge_sort();
	s.display();

	return 0;
}