From: Peter Wehrfritz <peter.wehrfritz@we...>  20070128 01:18:12

Nathan Ingersoll schrieb: > Nice work Peter, please commit. We should probably convert > ecore_file_ls to use these functions too. > > Do you have a sense of how many nodes it takes for the heapsort to > have a significant advantage? We could have a sort wrapper to choose > the appropriate sort based on the number of nodes, but expose both > api's for apps that want to be certain which algorithm is chosen. > Here are two graphs that shows the behavior of the two algorithms once up to 50,000 nodes and one up to 500,000 nodes. http://mowem.de/ecore/mergeheap.pdf http://mowem.de/ecore/mergeheap2.pdf To determine where the heap is actually better then the merge sort here is a third graph that shows the time that the merge sort needed relative to the heap sort. As you can clearly see here it is about 80,000 nodes. http://mowem.de/ecore/mergeheap3.pdf So the wrapper should probably start at this value to use the heap sort. If you want to make some test on your own, you can find my test program under: http://mowem.de/ecore/ecore_list_sort.c Hope that helps you Peter 