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

Review request for Dolphin and Frank Reininghaus.


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

  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/20130206/add7707f/attachment.htm>