Fairly often we have to sort the sequence of objects during solving of problem. I think that Divide and Conquer algorithms are the most effective in solving problem of sortings, here is two of them:

Quick sort algorithm [C++]:

template <typename T>
void quick_sort(T* a, std::size_t begin, std::size_t end) {
	std::size_t i = begin, j = end;
	T x = a[ (begin+end)/2 ];
		do {
		while (a[i] < x) ++i;
		while (a[j] > x) --j;
			if (i <= j) {
			if (i < j) { std::swap(a[i], a[j]); }
			++i; --j;
		}
	} while (i <= j);

	if (i < end)
		quick_sort(a, i, end);
	if (begin < j)
		quick_sort(a, begin, j);
}

Merge sort algorithm [C++]:

template <typename T>
void merge(T * a, std::size_t begin, std::size_t center, std::size_t end) {
	std::size_t i = begin, j = center+1, t = 0;  
	T* buf = new T[end-begin+1];

	while (i <= center && j <= end) {
		if (a[i] < a[j])
			buf[t++] = a[i++];
		else
			buf[t++] = a[j++];
	}

	while (j <= end)	buf[t++] = a[j++];
	while (i <= center)	buf[t++] = a[i++];

	for (t = 0; t < end-begin+1; t++)
		a[begin+t] = buf[t];

	delete [] buf;
}

template <typename T>
void merge_sort(T* a, std::size_t begin, std::size_t end) {
	if (begin < end) {
		std::size_t split = (begin+end)/2;
		merge_sort(a, begin, split);
		merge_sort(a, split+1, end);
		merge(a, begin, split, end);
	}
}

Perfomance:

         | quick sort | merge sort 
---------|------------|------------
best     | O(n log n) | O(n log n)
average  | O(n log n) | O(n log n)
worst    | O(n^2)     | O(n log n) 

As you can see in theory quick_sort not so effective beside merge_sort. But some test and measuring of used time, gives:

Merge sort practice tests
1000000 elements 0.24 sec
	+ 0.20
2000000 elements 0.44 sec
	+ 0.20
3000000 elements 0.64 sec
	+ 0.20
4000000 elements 0.84 sec
	+ 0.22
5000000 elements 1.06 sec
	+ 0.17
6000000 elements 1.23 sec
	+ 0.24
7000000 elements 1.47 sec
	+ 0.21
8000000 elements 1.68 sec
	+ 0.20
9000000 elements 1.88 sec
	+ 0.20
10000000 elements 2.08 sec

Quick sort practice tests
1000000 elements 0.19 sec
	+ 0.18
2000000 elements 0.37 sec
	+ 0.16
3000000 elements 0.53 sec
	+ 0.18
4000000 elements 0.71 sec
	+ 0.17
5000000 elements 0.88 sec
	+ 0.23
6000000 elements 1.11 sec
	+ 0.15
7000000 elements 1.26 sec
	+ 0.16
8000000 elements 1.42 sec
	+ 0.21
9000000 elements 1.63 sec
	+ 0.17
10000000 elements 1.80 sec

Here is code of tests, please, share with results of test on your local machine at comments.

#include <iostream>
#include <cassert>
#include <cstdlib>
#include <cstdio>
#include <ctime>

#include "sort.hpp"

#define SIZE			10000000
#define START			1000000
#define DIFF			1000000

using namespace std;

/* merge sort testing */
void test_merge_sort() {

	printf("\nMerge sort practice tests\n");
	uint8_t * a = new uint8_t [SIZE];
	for (uint8_t * i = a; i < a+SIZE; ++i)
		*i = rand()%256;
	float elapsed_time, prev_elapsed_time = 0;

	for (size_t size = START; size <= SIZE; size += DIFF) {
		clock_t begin = clock();
		merge_sort(a, 0, size-1);
		clock_t end = clock();

		elapsed_time = float(end - begin) / CLOCKS_PER_SEC;

		if (prev_elapsed_time != 0)
			printf("\t+ %.2f\n", elapsed_time-prev_elapsed_time);

		prev_elapsed_time = elapsed_time;

		for (uint8_t * i = a; i+1 < a+size; ++i) assert(*i <= *++i);

		printf("%d elements %.2f sec\n", size, elapsed_time);
	}
}

/* quick sort test */
void test_quick_sort() {

	printf("\nQuick sort practice tests\n");
	uint8_t * a = new uint8_t [SIZE];
	for (uint8_t * i = a; i < a+SIZE; ++i)
		*i = rand()%256;
	float elapsed_time, prev_elapsed_time = 0;

	for (size_t size = START; size <= SIZE; size += DIFF) {
		clock_t begin = clock();
		quick_sort(a, 0, size-1);
		clock_t end = clock();

		elapsed_time = float(end - begin) / CLOCKS_PER_SEC;

		if (prev_elapsed_time != 0)
			printf("\t+ %.2f\n", elapsed_time-prev_elapsed_time);

		prev_elapsed_time = elapsed_time;

		for (uint8_t * i = a; i+1 < a+size; ++i) assert(*i <= *++i);

		printf("%d elements %.2f sec\n", size, elapsed_time);
	}
}

int main() {
	test_merge_sort();
	test_quick_sort();

	return 0;
}