Messages in this thread | | | Date | Fri, 13 Nov 1998 20:31:56 +0100 | From | Matthias Andree <> | Subject | Re: 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/
| |