Re: elevator algorithm bug in ll_rw_blk.c

Matthias Andree (mandree@sx1.HRZ.Uni-Dortmund.DE)
Fri, 13 Nov 1998 20:31:56 +0100

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.

-- 
Matthias Andree


-
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/