quick sort of single linked list

list_quick_sort.h

#pragma once
#include <utility>
//
// Quick sort for single linked list
// 
// Template arguments:
// T: node's pointer type
// Next: function/functor to get next node
// Compare: functor to compare 2 arguments
// 
// Functions:
// partition: partition the list into 2 parts, with the pivot at the middle
// quick_sort: recurisve sort left and right part
//
template <class T, class Next, class Compare>
std::pair<T, T> partition(T start, T end, Next next, Compare comp)
{
	// use the first element as pivot as it is easier to access
	T pivot = start; 

	// in process of partition, there are 4 part of datas:
	// pivot | less than pivot | larger than pivot | not processed |
	//
	// first, initialize sLast and lLast to the pivot 
	T sLast = start;
	T lLast = start; 

	// start to process each element after pivot
	T iter = next(start); 
	while(iter != end)
	{
		T cur = iter;
		iter = next(iter);

		if(comp(cur, pivot)) 
		{
			// insert current to the next of sLast, only if we already have some elements larger than pivot
			if(lLast != pivot)
			{
				// insert after sLast
				T temp = next(sLast);
				next(sLast) = cur;
				next(cur) = temp;

				// as cur is removed, we need to link the 2 node before and after
				next(lLast) = iter;
			}

			// advance sLast
			sLast = cur;
		}
		else
		{
			// advance lLast
			lLast = cur;
		}
	}

	T head = next(pivot);

	// Insert pivot to the correct position if there is no element less than pivot
	if(sLast != pivot) 
	{
		T temp = next(sLast);
		next(sLast) = pivot;
		next(pivot) = temp;
	}

	return std::make_pair(head ,pivot);
}


// TODO: merge sort, insert sort! and compare them

template <class T, class Next, class Compare>
T quick_sort(T start, T end, Next next, Compare comp)
{
	// base case - only one element in the list
	if(start == end) return start;
	if(start != NULL && next(start) == end) return start;
	if(end != NULL && next(end) == start) return end; // think about already sorted list

	// divide
	std::pair<T, T> pos = partition(start, end, next, comp);

	// and conquer
	T head1 = quick_sort(pos.first, pos.second, next, comp);
	T head2 = quick_sort(next(pos.second), end, next, comp);

	// link the first part and the second part, or else you may drop some elements
	next(pos.second) = head2;

	return head1;
}