template <typename ItemType, typename ADT>
void Sort<ItemType,ADT>::quickSort(void)
{
//  implement this function!
//
//  call internal function:
    _quickSort(items.begin(), --items.end());
}

template <typename ItemType, typename ADT>
void Sort<ItemType,ADT>::_quickSort(typename ADT::iterator first, typename ADT::iterator last)
{
    typename ADT::iterator pivot, left_side, right_side;
    pivot=first;//will always set our pivot equal to first item!!!
    left_side=last;//lesser number come left to the pivot
    right_side=++first;//greater number come right of the pivot
    --first;//recover actual value of first
    cout<<__LINE__<<"Before while"<<endl;
    while(*left_side<*right_side)
    {
        cout<<__LINE__<<"Inside while"<<endl;
        cout<<__LINE__<<"left_side"<<*left_side<<endl;
        cout<<__LINE__<<"right_side"<<*right_side<<endl;
        --left_side;
        while(*left_side < *pivot);
        cout<<__LINE__<<"Inside 2nd while"<<endl;
        while(right_side != items.begin() && *--right_side > *pivot);
        cout<<__LINE__<<"inside 3rd while"<<endl;
        if(*left_side < *right_side)
        {
            swap(*left_side, *right_side);
        }//end if
    }//end while
    swap(*left_side, *first);
    _quickSort(first, --left_side);
    _quickSort(++left_side, last);

}//end _quickSort