Originally Posted by
iMalc
Okay so you have an array of linked-lists (all of which happen to be the same length) and you want to sort is such that of all the n elements, the k lowest are in the first list and the next k lowest are in the next list etc. Clearly items do not necessarily end up in the bucket they started in.
What this all says to me is that you should do this via the following three steps:
Step 1: Join all of the linked-lists together
Step 2: Use a linked-list implementation of a sorting algorithm
Step 3: Cut the list up into lists of the original size and store each head back into the original array.
So, I hate to break it to you, but your array-based implementation of quicksort is not going to be of much use to you here.
It looks to me like the only reason for having the array of lists at all as opposed to keeping it as one list afterwards, is that you can perform lookups faster on this structure by doing a binary search based on the head items in the array. This gives you O(log(n/k) + k) lookup time, where k is the list length and n is the total number of items. I would just pick a better data structure than a list to begin with.