> > Replace O(n^2) list sort with an O(n log n) merge sort. > > The merge sort is based on the solution suggested in: > > http://cslibrary.stanford.edu/105/LinkedListProblems.pdf > > Tested sort_rules() improvement: > > 100K rules: O(n^2): 31382 milliseconds; O(n log n): 10 milliseconds > > 259K rules: O(n^2): 133753 milliseconds; O(n log n): 22 milliseconds > > > > Signed-off-by: Mark Smith <marsmith at akamai.com> > > Acked-by: Konstantin Ananyev <konstantin.ananyev at intel.com>
Applied, thanks
