```#include<iostream>
#include<algorithm>
#include<iterator>
#include<vector>
#include<string>

using namespace std;

template <class Iter>
void myQuickSort(Iter low, Iter high){ //Implement this.
//	cout << "Call=";
//	for_each(low,high, print);
//	cout << endl;
if ((high-low) <= 5)
sort(low,high);
else {
//sort low, middle, high
Iter last(high -1); //because high points beyond last element
int distanceToMid = (high -low ) /2;
Iter mid = low + distanceToMid;
if (*mid < *low)
swap(*low, *mid);
if (*last < *low)
swap(*last, *low);
if (*last < *mid)
swap (*mid, *last);

//move pivot to last position
swap(*mid, *last);

//		for_each(low,high, print);
//		cout << "---";
//begin partitioning
Iter i(low);
Iter j(last);
for (;;){
while(*(++i) < *last);
while(*last < *(--j));
if (i < j)
swap(*i, *j);
else
break;
}
swap(*i, *last);//restore pivot
//		for_each(low,high, print);
//		cout << endl;
myQuickSort(low, i); //i because the end is one beyond last element
myQuickSort(i+1, high);
}
};

template <class Any>
class Order {
public:
int place;
Any object;
Order() : place(0) {}; //cant initialize object
Order(int p, Any & o) : place(p), object(o) {};
bool operator<(const Order & o) {
if (object == o.object)
return place < o.place;
return object < o.object;}
bool operator==(const Order & o) {
return object == o.object;}
};

template <class Iter>
void myStableQuickSort(Iter low, Iter high){ //Implement this.
vector<Order<Person> > v;
//NOTE: The RIGHT way of doing this (which makes is work for ANY
// class) is with:
//typedef typename std::iterator_traits<Iter>::value_type elementType;
//vector<Order<elementType> > v;
// but this does not work in VC++ 6.0 since it does not support
// partial template specialization. Maybe one of you can think of a way
// to implement this so that it will work for any container.
int j;
Iter i(low);
for (j =0; i != high; ++i, ++j){
Order<Person> o(j,*i);
v.push_back(o);
};
myQuickSort(v.begin(), v.end());

//rewrite the old array with the new contents
vector<Order<Person> >::iterator k;
i = low;
for (k = v.begin(); k != v.end(); ++k, ++i){
*i = (*k).object;
}
}

class Person { //You CANNOT CHANGE anything in this class.
string name;
int id;
public:
Person() : name("") {};
Person(const string & s, int i) : name(s), id(i) {};
Person(const Person & p) : name(p.name), id(p.id) {}; //copy const.
bool operator<(const Person & p) const{
return name < p.name;};
bool operator==(const Person & p) const{
return name == p.name;};
friend ostream & operator<<(ostream & os, const Person & p){
os << p.name << " - " << p.id; return os;};
};

void print(int e){
cout << e << ' ';
};

int main() {
vector<int> v;
v.push_back(9); v.push_back(2); v.push_back(4);
v.push_back(5); v.push_back(7); v.push_back(3);
v.push_back(8); v.push_back(1); v.push_back(10);
v.push_back(19); v.push_back(12); v.push_back(14);
v.push_back(15); v.push_back(17); v.push_back(13);
v.push_back(18); v.push_back(11); v.push_back(110);

for_each(v.begin(), v.end(), print);
cout << endl;
//Note that v.end() refers to one element BEYOND, the last one.
//You should remember this when debugging your program.
myQuickSort(v.begin(),v.end());
for_each(v.begin(), v.end(), print);
cout << endl;

vector<Person> people;
Person p1("joe", 1); people.push_back(p1);
Person p2("joe", 1); people.push_back(p2);
Person p3("joe", 2); people.push_back(p3);
Person p4("joe", 2); people.push_back(p4);
Person p5("homer", 5); people.push_back(p5);
Person p6("marge", 3); people.push_back(p6);
Person p7("bart", 5); people.push_back(p7);
Person p8("lisa", 8); people.push_back(p8);
Person p9("joe", 4); people.push_back(p9);
Person p10("joe", 4); people.push_back(p10);

myStableQuickSort(people.begin(), people.end());
vector<Person>::iterator it;
for (it = people.begin(); it != people.end(); ++ it)
cout << *it << endl;
return 0;
}```