Implementing a iterator based shell sort

Question

My shell sort looks like this:

template<class T>
void shellSort(T *begin, T *end) {
    int shell = 1;

    while (shell < (begin - end) / 3) shell = shell * 3 + 1;
    while (shell > 0) {
        for (auto index = shell; index < end; index++) {
            for (auto insertion = index; insertion >= shell && *(insertion - shell) > *(insertion); insertion -= shell) {
                swap(*(insertion - shell), *(insertion));
            }
        }

        shell = shell / 3;
    }
}

Pretty run of the mill. The problem I'm running into is on this line:

for (auto index = shell; index < end; index++)

Since shell is an int but end is an int * it doesn't know how to do the comparison. How do I go about resolving this?

Answer 1

Use "iterators" for addressing items, and use integers for relative offsets only:

for (auto index = begin + shell; index < end; ++index) ...

By the way, you probably want shell < (end - begin)/3, not (begin - end).

Answer 2

Assuming these are random access iterators, since the performance will be pretty bad otherwise.

You can use std::distance to get the difference between two iterators. You can also use std::advance to add an integer to an iterator.