Sorting optimization - high level strategies wanted

#include <stdio.h>
#include <stdlib.h>
#include <windows.h>
#include <mmsystem.h> //for timeGetTime()
#include <vector>
#include <list>
#include <algorithm>

using std::vector;
using std::list;

static DWORD gs_nStartTime = 0;

#pragma comment(lib, "winmm.lib") //for mmsystem.h

void StartTimer() {
	gs_nStartTime = timeGetTime();
}

void StopTimer(LPSTR szName) {
	printf("%s sort took %ums\n", szName, timeGetTime() - gs_nStartTime);
}

struct error_node {
	float err; // error value used to sort the list
	int ind; // index of edge
};

//Create some variable types for convenience
typedef list<error_node> edge_head_t;
typedef vector<edge_head_t::iterator> edge_map_t;
typedef vector<error_node> sort_edge_t;

//This is your compare function
//Note that it is passed by value. This creates a copy of both
//"first" and "second" every time this function is called.
bool StdCompare(error_node first, error_node second) {
	if (first.err >= second.err) {
		return false;
	}
	return true;
}

int QSortCompare(const void *pElem1, const void *pElem2) {
	if (((error_node *)pElem1)->err < ((error_node *)pElem2)->err) { //less than
		return -1;
	} else if (((error_node *)pElem1)->err > ((error_node *)pElem2)->err) { //greater than
		return 1;
	}
	return 0; //equal
}

//This is your sorting algorithm:
void YourSort(float *pEdgesArray, unsigned nEdges, unsigned *pDirtyArray, unsigned nDirtyEdges) {
	edge_head_t edge_head;  // list of mesh edges
	edge_map_t edge_map; // vector of iterators that point to each edge in egde_head
	sort_edge_t sort_edge; // vector of dirty edges
	//Setup
	//edge_head
	for (unsigned nEdge = 0; nEdge < nEdges; ++nEdge) {
		error_node enNew;
		enNew.ind = nEdge;
		enNew.err = pEdgesArray[nEdge];
		edge_head.insert(edge_head.end(), enNew);
	}
	//edge_map
	for (edge_head_t::iterator iEdge = edge_head.begin(); iEdge != edge_head.end(); ++iEdge) {
		edge_map.push_back(iEdge);
	}
	//sort_edge
	for (unsigned nEdge = 0; nEdge < nDirtyEdges; ++nEdge) {
		error_node enNew;
		enNew.ind = pDirtyArray[nEdge];
		enNew.err = pEdgesArray[enNew.ind];
		sort_edge.push_back(enNew);
	}
	//Now start the timer and sort
	StartTimer();
	if (!sort_edge.empty()) {
		std::sort(sort_edge.begin(), sort_edge.end(), StdCompare); // sort edges into ascending `err` values
		// next for loop removes dirty edges from edge_head leaving an incomplete but sorted list
		sort_edge_t::iterator vec;
		for (vec = sort_edge.begin(); vec != sort_edge.end(); ++vec){ //NOTE: ++vec is faster than vec++, especially for iterators
			// erase edge with index ind using edge_map which is an indexing of the error_nodes in edge_head e.g. suppose (*vec).ind == 10 then edge_map[10] is an iterator to the error_node with index 10 in edge_head list
			edge_head.erase(edge_map[(*vec).ind]);
		}
		//next bit of code inserts the dirty edges back into the list in the right order
		vec = sort_edge.begin();
		for (edge_head_t::iterator lis = edge_head.begin(); lis != edge_head.end(); ++lis){
			if ((*lis).err >= (*vec).err){
				lis = edge_head.insert(lis, *vec);
				edge_map[(*vec).ind] = lis;
				++vec;
			}
			if (vec == sort_edge.end()) {
				break;
			}
		}
		// now insert the remaining dirty edges at the end of the list.
		while (vec != sort_edge.end()){
			edge_head.push_back(*vec);
			edge_map[(*vec).ind] = (--edge_head.end());
			++vec;
		}
		sort_edge.clear();
	}
	StopTimer("Your");
}

//Just a simple vector with no insert/remove
void SimpleStdVectorSort(float *pEdgesArray, unsigned nEdges) {
	sort_edge_t sort_edge; // vector of ALL edges
	//Setup
	//sort_edge
	for (unsigned nEdge = 0; nEdge < nEdges; ++nEdge) {
		error_node enNew;
		enNew.ind = nEdge;
		enNew.err = pEdgesArray[nEdge];
		sort_edge.push_back(enNew);
	}
	//Now start the timer and sort
	StartTimer();
	std::sort(sort_edge.begin(), sort_edge.end(), StdCompare); // sort edges into ascending `err` values
	StopTimer("std::vector");
}

//Using the ANSI qsort
void QSort(float *pEdgesArray, unsigned nEdges) {
	//Setup
	error_node *pNodes = new error_node[nEdges];
	for (unsigned nEdge = 0; nEdge < nEdges; ++nEdge) {
		pNodes[nEdge].ind = nEdge;
		pNodes[nEdge].err = pEdgesArray[nEdge];
	}
	//Now start the timer and sort
	StartTimer();
	qsort(pNodes, nEdges, sizeof(error_node), &QSortCompare);
	StopTimer("qsort");
	delete []pNodes;
}

//Testing
int SetupCompare(const void *pElem1, const void *pElem2) {
	if (*(float *)pElem1 < *(float *)pElem2) { //less than
		return -1;
	} else if (*(float *)pElem1 > *(float *)pElem2) { //greater than
		return 1;
	}
	return 0; //equal
}

int main() {
	printf("Setting up. Please wait.\n");
	//This is how many elements will be sorted.
	//You should change this to what you would expect to be your common case.
	//Results may vary widely if your common case is only 500, or 1,000,000
	const int nElements = 15000;
	//This is how many "dirty" elements will be in the array.
	//You should change this to what you would expect to be your common case.
	//Results may vary widely if your common case is 1% of the array or 95% of the array.
	const int nRandomElements = 1000; //1000 elements will be randomised again after the initial sort
	float *pSortArray = new float[nElements];
	unsigned *pDirtyArray = new unsigned[nRandomElements];
	for (int nElement = 0; nElement < nElements; ++nElement) {
		pSortArray[nElement] = rand() * 4.0f / RAND_MAX; //generate a bunch of random numbers in the range [0.0, 4.0)
	}
	qsort(pSortArray, nElements, sizeof(float), &SetupCompare);
	//We now have a completly sorted array.
	//Now inject a bit of randomness.
	for (int nElement = 0; nElement < nRandomElements; ++nElement) {
		bool bAlreadyExists;
		do {
			bAlreadyExists = false;
			pDirtyArray[nElement] = rand() % nElements;
			for (int nTest = 0; nTest < nElement; ++nTest) {
				if (pDirtyArray[nElement] == pDirtyArray[nTest]) {
					bAlreadyExists = true;
					break;
				}
			}
		} while (bAlreadyExists);
		pSortArray[pDirtyArray[nElement]] = rand() * 4.0f / RAND_MAX; //generate a bunch of random numbers in the range [0.0, 4.0)
	}
	printf("Starting sorts\n");
	YourSort(pSortArray, nElements, pDirtyArray, nRandomElements);
	SimpleStdVectorSort(pSortArray, nElements);
	QSort(pSortArray, nElements);
	delete []pDirtyArray;
	delete []pSortArray;
	return 0;
}

Setting up. Please wait.
Starting sorts
Your sort took 63ms
std::vector sort took 154ms
qsort sort took 4ms