title: Optimal Quicksort for Single Linked List
body: <p>I am working on implementing a quicksort function to sort singly linked lists. What algorithm would I have to use to accomplish this ? For a linked list it would take worst case O(N) for each comparison, instead of the usual O(1) for arrays. So what would the worst case complexity  be ?</p>
  
  <p>To sum up, what modifications do I need to make to the quicksort algorithm to have an optimal sorting algorithm and what would be the worst case complexity of the algorithm ? </p>
  
  <p>Thanks!</p>
  
  <p>I have an implementation below: </p>
  
  <pre><code>public static SingleLinkedList quickSort(SingleLinkedList list, SLNode first, SLNode last)
  {
      if (first != null &amp;&amp; last != null)
      {
          SLNode p = partition(list, first, last) ;
          quickSort(list,first,p) ;
          quickSort(list,p.succ, last) ;
      }
      return list ;
  }
  
  public static SLLNode partition(SinlgleLinkedList list, SLNode first, SLNode last)
  {
  
      SLNode p = first ;
      SLNode ptr = p.succ ;
  
      while (ptr!=null)
      {
          if (ptr.data.compareToIgnoreCase(p.data)&lt;0)
          {
              String pivot = p.data ;
              p.data =  ptr.data ;
              ptr.data = p.succ.data ;
              p.succ.data = pivot ;
              p = p.succ ;
          }
          ptr = ptr.succ ;
      }
      return p ;
  }
  </code></pre>