Sort a linked list using quick sort

Merge sort looks like a best choice for sorting the linked list.At a first appearance, merge sort may be a good  selection since the middle element is required to subdivide the given list into 2 halves, but we can easily solve this problem by moving the nodes alternatively to 2 lists.

We have discussed the sorting options for linked list here. Here we will discuss about quick sort.

Another O(n log n) sort that you can implement on linked lists is a modification of quicksort. Although the linked list version of quicksort is fast (still O(n log n) expected), it isn't nearly as fast as the in-place version that works on arrays due to the lack of locality effects from array elements being stored contiguously. However, it's a very beautiful algorithm as applied to lists.
The intuition behind quicksort is as follows:

1. If you have a zero- or one-element list, the list is sorted.
2. Otherwise:
   1. Choose some element of the list to use as a pivot, say first element.
   2. Split the list into three groups - elements less than the pivot, elements equal to the pivot, and elements greater than the pivot.
   3. Recursively sort the smaller and greater elements.
   4. Concatenate the three lists as smaller, then equal, then greater to get back the overall sorted list.

One of the nice aspects of the linked-list version of quicksort is that the partitioning step is substantially easier than in the array case. After you've chosen a pivot (details a bit later), you can do the partitioning step by creating three empty lists for the less-than, equal-to, and greater-than lists, then doing a linear scan over the original linked list. You can then append/prepend each linked list node to the linked list corresponding to the original bucket.
The one challenge in getting this working is picking a good pivot element. It's well known that quicksort can degenerate to O(n²) time if the choice of pivot is bad, but it is also known that if you pick a pivot element at random the runtime is O(n log n) with high probability. In an array this is easy (just pick a random array index), but in the linked list case is trickier. The easiest way to do this is to pick a random number between 0 and the length of the list, then choose that element of the list in O(n) time. Alternatively, there are some pretty cool methods for picking an element at random out of a linked list; one such algorithm is described here.