Parallel Sorting

[daviddoria]

I've seen a few questions about this floating around here (mostly from me :) ) but I finally got this is into a nice working form - maybe it will be useful for someone.

It is called like this:

void TestParallelSort()
{
	vector<double> Numbers;
	Numbers.push_back(3.4);
	Numbers.push_back(4.5);
	Numbers.push_back(1.2);
	
	vector<string> Names;
	Names.push_back("David");
	Names.push_back("Hayley");
	Names.push_back("Joe");

	Tools::ParallelSort(Numbers, Names);
		
	/*
	output should be
	1.2 Joe
	3.4 David
	4.5 Hayley
	*/
	
	//Tools::OutputVector(Indices);
	Tools::OutputVector(Numbers);
	Tools::OutputVector(Names);
}

And here is the code:

template <typename T>
	struct NumberedItem
	{
		unsigned int index;
		T Item;
	};

	template <typename T>
	bool operator<(NumberedItem<T> NI1, NumberedItem<T> NI2)
	{
		//return NI1.index < NI2.index;
		return NI1.Item < NI2.Item;
	}
	
	template <class T, class S>
	void ParallelSort(vector<T> &Things1, vector<S> &Things2)
	{
		//this function sorts Things1 and reorders Things2 so that it is in the same order as the sorted Things1
		assert(Things1.size() == Things2.size());
		
		unsigned int NumThings = Things1.size();
		
		//create the sortable objects
		vector<NumberedItem<T> > Pairs(NumThings);
		for(unsigned int i = 0; i < NumThings; i++)
		{
			Pairs[i].index = i;
			Pairs[i].Item = Things1[i];
		}
		
		sort(Pairs.begin(), Pairs.end());
		
		vector<unsigned int> SortedIndices(NumThings);
		for(unsigned int i = 0; i < NumThings; i++)
			SortedIndices[i] = Pairs[i].index;
		
		vector<T> Things1Out(NumThings);
		vector<S> Things2Out(NumThings);
		for(unsigned int i = 0; i < NumThings; i++)
		{
			Things1Out[i] = Pairs[i].Item;
			Things2Out[i] = Things2[SortedIndices[i]];
		}
		
		//return by reference
		Things1 = Things1Out;
		Things2 = Things2Out;
	}