Quick Sort

#include <type_traits>
#include <iostream>
#include <vector>
#include <array>
#include <utility>
#include <list>
#include <forward_list>


template <typename RandomIt, typename  Compare=std::less<typename std::iterator_traits<RandomIt>::value_type> >
void quicksort(RandomIt first, RandomIt last, const Compare &comp = Compare()){
    if(first + 1 >= last)
        return;
    decltype((*first)) pivot = *first;
//    RandomIt ptr = first, now = first;
//    for(;now != last; ++now)
//        if(comp(*now, pivot))
//            std::swap(*(++ptr), *now);
//    std::swap(*first, *ptr);
//    quicksort(first, ptr, comp);
//    quicksort(ptr + 1, last, comp);

    RandomIt left = first, right = last;
    while(left < right){
        while(comp(pivot,*(--right)));
        while(left < right && comp(*(++left), pivot));
        //if(left < right)
            std::swap(*left, *right);
    }
    std::swap(*left, *first);
    quicksort(first, left, comp);
    quicksort(left + 1, last, comp);
}

/*
template <typename RandomIt>
void msort(RandomIt first, RandomIt last){
    using T = typename std::remove_reference<decltype(*first)>::type;
    quicksort<RandomIt, std::less<T>>(first, last, std::less<T>());
};
*/



template <typename T>
struct LinkNode {
    T value;
    LinkNode<T> * next;
    LinkNode():next(nullptr), value(){}
    LinkNode(const T & val, LinkNode<T> * lk):next(lk), value(val){}
};

template <typename T>
LinkNode<T> * __link_sort(LinkNode<T> * &first){
    if(first == nullptr || first->next == nullptr){
        return first;
    }
    LinkNode<T> *ptr = first->next, *tmp, *left = nullptr, *right = nullptr, *left_last=nullptr, *right_last=nullptr;
    while(ptr){
        tmp = ptr;
        ptr = ptr->next;
        if(tmp->value < first->value){
            tmp->next = left;
            left = tmp;
        }
        else{
            tmp->next = right;
            right = tmp;
        }
    }
    left_last = __link_sort(left);
    right_last = __link_sort(right);
    if(left_last != nullptr)
        left_last->next = first;
    else
        left = first;
    first->next = right;
    if(right == nullptr)
        right_last = first;
    first = left;
    return right_last;
}


template <typename T>
void link_sort(T & head){
    __link_sort(head);
}

template <typename T>
LinkNode<T> * __link_msort(LinkNode<T> *&head, std::size_t sz){
    if(sz <=  1){
        return head;
    }
    std::size_t left_sz = sz / 2, right_sz = sz - left_sz;
    LinkNode<T> new_head, * ptr = &new_head, * left = head;
    LinkNode<T> * left_last = __link_msort(left, left_sz);
    LinkNode<T> * right = left_last->next;
    LinkNode<T> * right_last = __link_msort(right, right_sz);
    LinkNode<T> * end_next = right_last->next;
    while(left_sz && right_sz){
        if(left->value < right->value) {
            ptr = ptr->next = left;
            left = left->next;
            left_sz--;
        }else{
            ptr = ptr->next = right;
            right = right->next;
            right_sz--;
        }
    }
    if(right_sz)
        left = right, left_last = right_last;
    if(left_sz || right_sz){
        ptr->next = left;
        ptr = left_last;
    }
    ptr->next = end_next;
    head = new_head.next;
    return ptr;
}

template <typename T>
void link_msort(T & head, std::size_t sz){
    __link_msort(head, sz);
}

template<typename T>
LinkNode<T> * __quick_sort(LinkNode<T> * &first){
    if(first == nullptr || first->next == nullptr)
        return first;
    LinkNode<T> lower, upper, *left = & lower, *right = & upper, * pov = first;
    first = first->next;
    while(first){
        if(pov->value < first->value){
            right->next = first;
            right = first;
        }
        else{
            left->next = first;
            left = first;
        }
        first = first->next;
    }
    left->next = right->next = nullptr;
    left = __quick_sort(lower.next);
    right = __quick_sort(upper.next);
    if(left == nullptr)
        left = &lower;
    left->next = pov;
    first = lower.next;
    pov->next = upper.next;
    if(right == nullptr)
        right = pov;
    return right;
}

template <typename T>
void list_qsort(T & head){
    __link_sort(head);
}

template <typename T>
LinkNode<T> * make_list(const std::vector<T> & values){
    LinkNode<T> head, * tmp = nullptr;
    for(const T & val:values){
        tmp = new LinkNode<T>(val, head.next);
        head.next = tmp;
    }
    return tmp;
}

template <typename T>
void print(LinkNode<T> * head){
    while(head){
        std::cout<<head->value << " ";
        head = head->next;
    }
    std::cout<<std::endl;
}

int testmsort(){
    test_vector();
    std::forward_list<int> ls;
    std::list<int> lst;
    ls.sort();
    lst.sort();
    std::vector<int> vec ={3,2,1,4,5,1,2,3,4,5,6,7,8,9,10};
    //std::vector<int> vec ={2,4,3,4};
    LinkNode<int> * first = make_list(vec), *last=nullptr;
    print(first);
    //link_msort(first, vec.size() - 6);
    /*  */

    link_sort(first);
//    link_qsort(first);
    print(first);
    return 0;
}

int __textmsort = testmsort();
int main(){
    return 0;
}