Re: elevator algorithm bug in ll_rw_blk.c

Jamie Lokier (lkd@tantalophile.demon.co.uk)
Sun, 15 Nov 1998 09:23:40 +0000

Messages sorted by: [ date ][ thread ][ subject ][ author ]
Next message: Jamie Lokier: "Re: [2.1.128-ac2] Faster! AVL trees or asm changes?"
Previous message: Ragnar Hojland Espinosa: "Re: 2.1.127 / 128 problems... Subject summary..."

A non-recursive merge sort that identifies contiguous runs is extremely
fast for nearly-sorted lists, and also very fast for randomly ordered
and reversed ordered lists. The best case is O(n), worst case is
O(n log n).

And it only uses a tiny bit of RAM (just a few pointers).

The only requirement is that you have a singly-linked list of elements.

-- Jamie

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

Next message: Jamie Lokier: "Re: [2.1.128-ac2] Faster! AVL trees or asm changes?"
Previous message: Ragnar Hojland Espinosa: "Re: 2.1.127 / 128 problems... Subject summary..."