#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
#include <list>

using namespace std;

template<class Iterator>
class Sorter
{
public:
	virtual void sort(Iterator begin, Iterator end) const = 0;
};

template<class Iterator>
class BubbleSort : public Sorter<Iterator>
{
public:
	void sort(Iterator begin, Iterator end) const
	{
		// implement this yourself!
	}
};

template<class Iterator>
class StdSort : public Sorter<Iterator>
{
public:
	void sort(Iterator begin, Iterator end) const
	{
		std::sort(begin, end);
	}
};

template<class Iterator>
class InsertionSort : public Sorter<Iterator>
{
	typedef typename Iterator::value_type value_t;
	typedef list<value_t> storage_t;
public:
	void sort(Iterator begin, Iterator end) const
	{
		// implement me!
		// one hint: there is a function std::lower_bound() in the Algorithms library
		// that is very useful here
	}
};

template<class Iterator>
Sorter<Iterator> * sortingFactory(string algorithm)
{
	// implement me!
}

typedef double T;
typedef vector<T>::iterator iterator_t;

int main(int argc, char ** argv)
{
	if (argc != 2) {
		cerr << argv[0] << " <sorting algorithm>" << endl;
		exit(1);
	}
	
	Sorter<iterator_t> *mysort = sortingFactory<iterator_t>(string(argv[1]));
	
	vector<T> foo;
	copy(istream_iterator<T>(cin),
		istream_iterator<T>(),
		back_inserter(foo));
	
	mysort->sort(foo.begin(), foo.end());
	
	copy(foo.begin(), foo.end(), ostream_iterator<T>(cout, "\n"));
	cout << endl;
	
	delete mysort;
}