//
//	test of merge sort routine
//
//	Described in Chapter 8 of
//	Data Structures in C++ using the STL
//	Published by Addison-Wesley, 1997
//	Written by Tim Budd, budd@cs.orst.edu
//	Oregon State University
//

# include "vector.h"
# include <iostream.h>
# include <algo.h>

// the following is required by codewarrior,
// possibly other compilers, but not by g++
//# include <tempbuf.cpp>

template <class Itr>
void m_sort(Itr start, unsigned low, unsigned high)
{
	if (low + 1 < high) {
		unsigned int center = (high + low) / 2;
		m_sort (start, low, center);
		m_sort (start, center, high);
		inplace_merge (start + low, start + center, start + high);
		}
}

template <class T> 
void mergeSort(vector<T> & s)
{
	m_sort(s.begin(), 0, s.size());
}

void main() {
	vector<int> v(100);
	for (int i = 0; i < 100; i++)
		v[i] = rand();
	mergeSort(v);
	vector<int>::iterator itr = v.begin();
	while (itr != v.end()) {
		cout << *itr << " ";
		itr++;
		}
	// copy (v.begin(), v.end(), ostream_iterator<int>(cout, ":"));
	cout << "\n";
}