Re: Parallel quicksort
On 15-05-2010 19:47, markspace wrote:
Arne Vajh?j wrote:
} else {
ThreadSortHelp h1 = new ThreadSortHelp(n1, r, ia, depth + 1, tdepth);
ThreadSortHelp h2 = new ThreadSortHelp(l, n2, ia, depth + 1, tdepth);
Just a thought: Why spawn two threads here? You already have one thread
running (the current one). Spawn one thread (proabaly on the larger span
between pivot and start/end) and sort the other bit recursively in the
current thread. Then just wait on the other thread after you're done
with the recursive sort.
It may be more efficient. But I like the symmetric approach of
this code.
However, I played around with this myself a while ago, and I'm not sure
the whole idea is a great one. Quicksorts are god-awful at sorting many
real world types of data. If a list is already sorted, then quicksort
degenerates into a bubble sort. That's N^2 performance. And pre-sorted
data is pretty common so you're likely to hit this issue often.
Not quite correct.
Quicksort degenerate into O(n^2) for sorted data *if* the first
or last element is used as pivot.
My code used the middle element.
For the very same reason.
That works super for sorted data.
Ofcourse there still exists some orders that degenerate
into O(n^2), but they are not very likely (unlike the already
sorted order).
Arne