QuickSort C++ Implementation using Iterators I implemented quicksort using iterators. I am will be grateful, if someone can review my piece of code. BTW, I am just selecting the last element as the pivot (which I plan to randomize later) I am mainly looking for the following:

1) Correctness of the Implementation

2) Correct usage of iterators

3)  Basic coding style.

Although above are the key things I am looking for, please feel free to point out any mistakes. Thanks!!!

#include &lt;iostream&gt;
#include &lt;vector&gt;
#include &lt;algorithm&gt;
#include &lt;iterator&gt;
#include &lt;utility&gt;


typedef std::vector&lt;int&gt;::iterator itr;

itr partition(itr left,itr right)
{

    itr i=left-1;

    itr it=left;

    while(it&lt;right)
    {
        if(*it&lt;=*right)
        {
            ++i;
            std::swap(*i,*it);
        }
        ++it;
    }

    std::swap(*(i+1),*right); 
    return ++i;
}

void quicksort(std::vector&lt;int&gt;&amp; v,itr left, itr right)
{
    if(std::distance(left,right)&gt;=2)
    {
        itr q=partition(left,right);
        quicksort(v,left,q-1);
        quicksort(v,q+1,right);
    }
}


int main()
{
    std::vector&lt;int&gt; v={6,10,4,5,3,9,13,8};

    std::copy(v.begin(),v.end(),std::ostream_iterator&lt;int&gt;(std::cout," "));
    std::cout&lt;&lt;std::endl;

    quicksort(v,std::begin(v),std::end(v)-1);

    std::copy(v.begin(),v.end(),std::ostream_iterator&lt;int&gt;(std::cout," "));
    std::cout&lt;&lt;std::endl;


    return 0;
}
Templates

Sorting is pretty much the same regardless of the type of items being sorted, as long as you can compare and swap those things. Might as well implement the sorting and partitioning as templates so they can work for various containers and/or types in the containers.

Pass only what's needed

Right now, your quicksort receives the container to be sorted as a parameter. It also receives iterators referring to the beginning and end of the range to be sorted. It "uses" the container parameter only to pass it in further recursive calls--but none of the calls ever actually makes any real use of that parameter.

The parameter is never used, so you might as well not pass it.

At the same time, sorting an entire collection is common enough that it may well be worthwhile to provide that directly. For example:

// basic version that uses (only) iterators
template &lt;class Itr&gt;
void quicksort(Itr b, Itr e) {
    if (std::distance(b, e) &gt; 1) {
        Itr pivot = partition(b, e);
        quicksort(b, pivot);
        quicksort(pivot, e);
    }
}

// Version to sort a whole container
template &lt;class Container&gt;
void quicksort(Container &amp;c) { 
    quicksort(c.begin(), c.end());
}


Don't explicitly specify std::swap

If the user has defined a swap for the type of object being sorted, you want to use it. You only want to use std::swap if they haven't defined it. To do that, you typically have a using directive to make std::swap visible in the current scope, then make an unqualified call to swap. If they've defined a swap for their type, this will find their swap via argument dependent lookup. Then, if (and only if) that fails, it will find std::swap.

if(*it&lt;=*right)
{
    using std::swap;
    ++i;
    swap(*i,*it);
}


Decide what to support

Right now, you use std::distance to measure the distance between a pair of iterators. That lets the code work with most categories of iterators.

Unfortunately, you also use iterator + int, and that only works with random access iterators, so the code overall only works with random access iterators.

If you don't mind requiring random access iterators, then you might as well depend on them throughout, and just subtract iterators to get a distance.

Conversely, if you really want the code to work with other iterators, you should truly support that, such as by using std::advance or std::next to modify the pointers.

Minimize requirements on the contained type

Quicksort can be written so the only comparison it depends upon is operator&lt;. Right now you use &lt;= for no particularly good reason that I can see.