How do you write a quick sort program using linked list and recursive methods?

Answer 1

Although you can quicksort a linked list in place, the lack of constant-time random-access into the list makes this operation inefficient, particularly if you wish to make use of the median-of-three optimisation when selecting pivots. That is, locating the middle element in a partition of n elements in a list will take O(n/2) time, and that's an unacceptable overhead for a large n due to the sheer number of partitions. The only alternative is to use the first or last element when selecting a pivot as those are the only two elements you have constant time access to.

However, if memory is not an issue, you can easily construct a parallel array of bi-directional iterators into the list with a single traversal, taking O(n) time. Once you have an array of iterators you can efficiently sort it. You then have the option of using the array to access the list in sorted order or you can traverse the array to reconstruct the list, extracting each element in turn and pushing it to the end of the list. Thus the total overhead is O(n*2) time.