Q:

deduce the type of variable from iterator in a template, with out using auto

In the following code, I have used auto to define a new variable "temp" compatible with the iterator used. I am just curious whether I can do the same without using auto keyword??
In other words, I have no idea what the container is. So how can I define the temp variable without damaging the generality of the code.
Being a newbie to C++,I have been using SO as my go to site for any questions. I have looked for similar questions, but i didn't find any. Any help would be appreciated!!
/* InsertionSort.c */
#include<iostream>
#include <typeinfo>

namespace sort {

template <class RandomAccessIterator, class Compare >
void InsertionSort(RandomAccessIterator begin, RandomAccessIterator end, Compare comp) {
    RandomAccessIterator itrOuter,itrInner,itrShift;

    for(itrOuter = begin+1; itrOuter!=(end); itrOuter++) {
     // ***************HERE***********************************************   
             auto temp= *itrOuter;

        for(itrInner=begin;itrInner<itrOuter;itrInner++) {
            if(!comp(*itrInner,*itrOuter)) {
                for(itrShift=itrOuter;itrShift> itrInner;itrShift--)
                    *itrShift=*(itrShift -1);
            *itrInner=temp;
            break;
            }       
        }
    }       
}
}

bool Compa(int& x, int& y) {return (x<y);}

int main(void) {
    using namespace sort;
    int arr[] = {3,5,1,7,2,6,9,12};
    InsertionSort(arr, arr+8, Compa );

    for(int i=0;i < 8;i++) 
        std::cout<<arr[i]<<" ";

    return 0;
}

A:

Using auto is the easiest approach using C++11. You can also use decltype(), of course:
decltype(*itrOuter) tmp = *iterOuter;

which will, as your approach using auto, copy the value. If you actually want to get a reference you'd use
decltype((*itrOuter)) tmp = *iterOuter;

which is roughly equivalent to:
auto& tmp = *iterOuter;

Assuming you need to use C++03, there is no way to deduce the variable type in this location. The only approach deducing the variable type is to delegate to a function template. The normal C++03 approach is to obtain the value_type from std::iterator_traits<...>:
typename std::iterator_traits<RandomAccessIterator>::value_type tmp = *iterOuter;

... or, doing the same with a reference:
typename std::iterator_traits<RandomAccessIterator>::reference tmp = *iterOuter;

