Re: elevator algorithm bug in ll_rw_blk.c
kwrohrer@ce.mediaone.net
Fri, 13 Nov 1998 17:23:39 -0600 (EST)
And lo, Matthias Andree saith unto me:
>
> On Fri, Nov 13, 1998 at 05:24:37PM +1300, Chris Wedgwood wrote:
> > Perhaps my methods were broken, but sorting stuff before a sync. did
> > seem to help, except I used a quick-sort at the time and used to
> > overflow the stack...
>
> As everybody knows, Quick Sort is not immune to worst case condition,
> flooding your stack and rising its complexity to O(nē), which makes it
> inadequate for time-/memory-critical environments such as kernels. You
> might want to use some simpler algorithm which is stable, such as
> ShellSort or CombSort, and yet, if there are a LOT of entries to be
> sorted like around >>1,000 blocks, you might consider Heap Sort - I
> assume, Heap Sort would be overkill.
>
Why do we need a stable sort, unless time is one of the sort keys?
Merge sort or heap sort should do just fine, and IIRC heap sort
can be done in place without brain strain...
Keith
--
"The avalanche has already started; |Linux: http://www.linuxhq.com |"Zooty,
it is too late for the pebbles to |KDE: http://www.kde.org | zoot
vote." Kosh, "Believers", Babylon 5 |Keith: kwrohrer@enteract.com | zoot!"
www.midwinter.com/lurk/lurker.html |http://www.enteract.com/~kwrohrer | --Rebo
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/