[dm-devel] [PATCH 9/9] dm crypt: sort writes

[Akira Hayakawa]

> list_sort() uses merge sort, which has O(nlog(n)) complexity;
> list_sort() also suffers from "list passed to list_sort() too long for
> efficiency".  But in practice I'm not sure how long a list needs to be
> to hit that case.
> 
> Whereas an rb-tree has O(log(n)) complexity and is efficient for
> traversal, it also doesn't have the length limits.

I see. OK, I will remain on rb-tree.

Btw, if I want to disable sorting
1. Always attach new node to the left
2. Eliminate rb_insert_color()
is enough?

-- 
Akira