Review Request 108824: New sorting algorithm for Dolphin

[Emmanuel Pescosta]

-----------------------------------------------------------
This is an automatically generated e-mail. To reply, visit:
http://git.reviewboard.kde.org/r/108824/
-----------------------------------------------------------

(Updated Feb. 16, 2013, 6:19 p.m.)


Review request for Dolphin and Frank Reininghaus.


Changes
-------

Avoid some unnecessary lessThan calls (Use compare return value [int] instead)


Description
-------

Implemented a new sorting algorithm called Tim Sort which is a modified Merge Sort algorithm (http://svn.python.org/projects/python/trunk/Objects/listsort.txt) - Default sorting algorithm in Python and Java

Tim Sort is really fast for already sorted lists (Great for inserting new items, sort role changes - see benchmark 2, ...)

Some benchmarks (200k folders and files):
# Sort Type: Name => TimSort: 1755 ms - Parallel MergeSort: 1547 ms
# Sort Type: Name (Reorder descending) => TimSort: 163 ms - Parallel MergeSort: 434 ms
# Sort Type: Size => TimSort: 259 ms - Parallel MergeSort: 516 ms
# Sort Type: Type => TimSort: 269 ms - Parallel MergeSort: 594 ms

Btw.: Tim Sort uses only 1 core!

ToDo: Write a benchmark for sorting algorithms


Diffs (updated)
-----

  dolphin/src/kitemviews/kfileitemmodel.h 903291a 
  dolphin/src/kitemviews/kfileitemmodel.cpp a763b3f 
  dolphin/src/kitemviews/private/kfileitemmodelsortalgorithm.h 1d56894 

Diff: http://git.reviewboard.kde.org/r/108824/diff/


Testing
-------

Sorting works fine for me


Thanks,

Emmanuel Pescosta

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mail.kde.org/mailman/private/kfm-devel/attachments/20130216/b764dc33/attachment.htm>