Matthias Clasen <matthias.cla...@gmail.com> writes: > > Next I implemented sorting. Because I use an array, I can use qsort(), > > which is fast. I had thought about switching to GSequence to get ever > > closer to GtkListStore, but I did not do that, and one of the reasons > > is that GSequence uses insertion sort, which is quite slow. > > Not sure why you keep repeating this, it is not true. GSequence is > backed by a balanced tree, so sorting by insertion gives you O(n log > n), so at least asymptotically, > it is fine. The implementation may of course still be slower than > qsort().
GSequence is indeed implemented with a randomized, balanced binary tree (a treap[1] to be specific), so sorting is expected O(n log n). While sorting a linked data structure is going to be slower than qsort() on an array, 1 second for 40,000 elements sounds wrong, so I'd be interested in seeing the benchmark. Thanks, Soren [1] http://en.wikipedia.org/wiki/Treap _______________________________________________ gtk-devel-list mailing list gtk-devel-list@gnome.org http://mail.gnome.org/mailman/listinfo/gtk-devel-list