Template Metaprogramming is best described by Wikipedia as

Templates are very useful and powerful in C++ and make your code more reusable. In this tutorial I will demonstrate how to generalize Selection Sort, Insertion Sort, and Bubble Sort so that they will work with a vector of any classes that can be compared. I have included a custom date class that can be used with it.

To start well create a header file named "sort.h" and add compiler guards and the imports we will use.

#ifndef SORT_H
#define SORT_H

#include <vector>
#include <iostream>
#include <fstream>
#include "date.h"
#include "except.h"
using namespace std;

Selection sort:
Is the simplest of sorting algorithms and is efficient on small list but suffers exponentially on larger list. Specifically it's Big-O notation is O(n^2).

The basic algorithm:
1. Find the smallest value in the list and swap it with the first
2. Find the next smallest value in the list and swap it with the second
3. Wash, Rinse, Repeat.

Here is what this would look like for a normal vector of ints.

unsigned int selectionSort(vector<int>& v) {
  for (unsigned int pass = 0; pass < v.size(); pass++) {
    unsigned int smallIndex = pass;
    for (unsigned int j = pass + 1; j < v.size(); j++) {
      if (v[j] < v[smallIndex]) {
	smallIndex = j;
      }
    if (pass != smallIndex) {
      T temp = v[pass];
      v[pass] = v[smallIndex];
      v[smallIndex] = temp;
    }
    }
  }
} 

Now to make this into a template we you have to do a couple of things. First we have to declare that it is a template and declare a typename with template <typename T> . This tells the compiler we are making a template and that anything declared as the type T is to be bound at compile time. (Note: This is not the same as run-time binding like many other OO Languages have)

Now we have:

unsigned int selectionSort(vector<T>& v) {
  for (unsigned int pass = 0; pass < v.size(); pass++) {
    unsigned int smallIndex = pass;
    for (unsigned int j = pass + 1; j < v.size(); j++) {
      if (v[j] < v[smallIndex]) {
	smallIndex = j;
      }
    if (pass != smallIndex) {
      T temp = v[pass];
      v[pass] = v[smallIndex];
      v[smallIndex] = temp;
    }
    }
  }
} 

Now we cad to the same for Insertion Sort. Insertion sort is easy to implement but is not very efficient on larger lists. The best explanation I have found for it (better than I can do) is at Softpanorama.

// Insertion Sort 
template <typename T>
unsigned int insertionSort(vector<T>& v) {
  unsigned int i, j, n = v.size();
  T target;
  for(i = 1; i < n; i++ ) {
    j = i;
    target = v[i];
    while (j > 0 && target < v[j-1]) {
      v[j] = v[j-1];
      j--;
    }
    v[j] = target;
  }
}

And now for Bubble Sort. Bubble sort works exactly the way you think it would. The small elements bubble up to the top while the larger elements sink to the bottom. The algorithm runs until there are no swaps made or your index is one element from the end. There is also a good explanation of this on Softpanorama.

template <typename T>
unsigned int bubbleSort(vector<T>& v) {
  unsigned int i = 0, n = v.size();
  bool swapped = true;
  T temp;
  while ((swapped == true)&&(i < n)) {
    swapped = false;
    if (v[i +1] < v[i]) {
      temp = v[i];
      v[i] = v[i +1];
      v[i + 1] = temp;
      swapped = true;
      i++;
    }
  }
  return Count;
}

To finish of the "sort.h" file we need to add our last compiler gaurd. #endif
There are three templates, you can find them along with all of the files to run and example that count how many operations each sort takes. There is a make file and several example input files. To run it type make in it's folder and the ./count <input file>. This has only been tested and run on *nix platforms. (Note these are from an old programming assignment so disregard some random comments.)