C++ generic insertion sort

Question

I am creating this to try get a better understanding of sorting algorithms and generic functions. I have implemented a basic insertion sort algorithm and I am trying to make it work with multiple data structures (lists and arrays at least).

Since I can access lists like this : list[N] to get the value, I think I need to be using iterators. So I am trying to convert my solution. Here is the basic insertion sort algorithm I am trying to modify:

int *insertionsort(int *a)
{
  for (int i = 1; i<length(a); ++i)
  {
    int k = a[i];
    int j = i-1;
    {
      while (j>=0 && a[j] > k)
      { 
        a[j+1] = a[j--];
      }
    a[j+1] = k;
  }
  return a;
}

And here is what I have so far for the generic version:

template <class T>
T insertionsort(T a)
{
  for (auto i = a.begin()+1; i<a.end(); ++i)
  {
    auto k = i;
    auto j = i-1;
    while (j>=a.begin() && *j>*k)  
    {
      (j + 1) = j--; 
    }
    (j + 1) = k;
  }  
   return a;
} 

Unfortunatley I can't seem to get this generic function to sort correctly at all. I have been looking at this quite a while with no luck. Ideas?

Answer 1

Posted only for the OP's reference, and not likely to live a long life. If you're so inclined to use C++11 and don't like typing, this may do the trick.

template<typename Iter>
void insertion_sort(Iter first, Iter last)
{
    for (Iter it = first; it != last; ++it)
        std::rotate(std::upper_bound(first, it, *it), it, std::next(it));
}

Relavent links for the functions used:

std::upper_bound, std::next, and std::rotate. Enjoy.

Answer 2

I think that you are confused with dereferencing iterators/pointers. This should work:

template <class T>
T insertionsort(T a)
{
    if(a.begin() == a.end()) // return a when it's empty
        return a;
    for(auto i = a.begin() + 1; i < a.end(); ++i)
    {
        auto k = *i; // k is the value pointed by i
        auto j = i - 1;
        while(j >= a.begin() && *j > k)  
        {
            *(j + 1) = *j; // writen in 2 lines for clarity
            j--;
        }
        *(j + 1) = k;
    }  
    return a;
}