title: What is the best in place sorting algorithm to sort a singly linked list
body: <p>I've been reading on in place sorting algorithm to sort linked lists. As per Wikipedia </p>
  
  <blockquote>
    <p>Merge sort is often the best choice for sorting a linked list: in this situation it is relatively easy to implement a merge sort in such a way that it requires only <code>Θ(1)</code> extra space, and the slow random-access performance of a linked list makes some other algorithms (such as quicksort) perform poorly, and others (such as heapsort) completely impossible.</p>
  </blockquote>
  
  <p>To my knowledge, the  merge sort algorithm is <em>not</em> an in place sorting algorithm, and has a worst case space complexity of <code>O(n)</code> auxiliary. Now, with this taken into consideration, I am unable to decide if there exists a suitable algorithm to sort a singly linked list with <code>O(1)</code> auxiliary space.</p>