Привет! Как выглядит быстрая сортировка (Хоара) для однонаправленного списка?

Question

Ну, впрнципе сам алгоритм я понимаю, и как перенести тоже (так же разбить на два подсписка, в одном - элементы больше выбранного, во втором - меньше, но все мои варианты немного "кривые" и достаточно сложные. 
 
Хотелось бы увидеть код на каком-нибудь ЯП или что-то еще полезное. Всем спасибо, кто откликнется.

*Перенести - всмысле применить (изменив) реализацию для массива - к списку

Людмила · Accepted Answer

На Си: 
 
Node* mysort(Node* list) 
{ 
 Node *pivot, *less, *ge, *tmp; 
 if(!list || !list->next) return list; 
 pivot = list; less = 0; ge = 0; 
 list = list->next; 
 while(list) 
 { 
 tmp = list->next; 
 if(list->key < pivot->key){ list->next = less; less = list; } 
 else{ list->next = ge; ge = list; } 
 list = tmp; 
 } 
 less = mysort(less); 
 ge = mysort(ge); 
 
 pivot->next = ge; 
 if(less) 
 { 
 for(tmp = less; tmp->next; tmp = tmp->next); 
 tmp->next = pivot; 
 return less; 
 } 
 return pivot; 
}