lkml.org 
[lkml]   [1998]   [Nov]   [13]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: elevator algorithm bug in ll_rw_blk.c
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/

\
 
 \ /
  Last update: 2005-03-22 13:45    [W:1.587 / U:0.752 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site