Having cured the many bugs in my "simple" implementations, I now have a slightly more conventional set of results:
The raw figures are at <http://www.bergbland.info/2secs.txt> and here. A spreadsheet... get <http://www.bergbland.info/2secs.ods>. The first section is the test code running with calls to a dummy routine that actually doesn't even try to sort the data, so the final column shows the time taken to shuffle the data. The figures there have already been incorporated in the later sections. As before, every test was run for two seconds and the result is the average time per execution of the particular sort routine. The figures in parentheses are the result of dividing the time by n*ln(n). Lines of code: quicksort:85(unreadable), heapsort:26(fairly obscure), mergesort:25(readable). My mergesort performs pretty badly. Not too surprising, as it's the shortest piece of code. :-) nosort: 1000 691ns(0ns) 678ns(0ns) 96620ns(13ns) 2000 682ns(0ns) 705ns(0ns) 192us(12ns) 3000 718ns(0ns) 717ns(0ns) 291us(12ns) 4000 720ns(0ns) 718ns(0ns) 389us(11ns) 5000 718ns(0ns) 719ns(0ns) 483us(11ns) 6000 717ns(0ns) 719ns(0ns) 581us(11ns) 7000 723ns(0ns) 720ns(0ns) 682us(11ns) 8000 721ns(0ns) 718ns(0ns) 785us(10ns) 9000 718ns(0ns) 719ns(0ns) 877us(10ns) quicksort: 1000 44699ns(6ns) 44881ns(6ns) 45895ns(6ns) 2000 89409ns(5ns) 88934ns(5ns) 94820ns(6ns) 3000 136us(5ns) 136us(5ns) 146us(6ns) 4000 181us(5ns) 180us(5ns) 198us(5ns) 5000 225us(5ns) 226us(5ns) 245us(5ns) 6000 271us(5ns) 270us(5ns) 295us(5ns) 7000 316us(5ns) 314us(5ns) 340us(5ns) 8000 362us(5ns) 361us(5ns) 387us(5ns) 9000 406us(4ns) 404us(4ns) 447us(5ns) heapsort: 1000 88687ns(12ns) 89078ns(12ns) 90234ns(13ns) 2000 176us(11ns) 179us(11ns) 194us(12ns) 3000 271us(11ns) 270us(11ns) 284us(11ns) 4000 359us(10ns) 360us(10ns) 373us(11ns) 5000 448us(10ns) 450us(10ns) 471us(11ns) 6000 538us(10ns) 544us(10ns) 595us(11ns) 7000 644us(10ns) 645us(10ns) 670us(10ns) 8000 724us(10ns) 719us(10ns) 759us(10ns) 9000 814us(9ns) 817us(9ns) 893us(10ns) mergesort: 1000 271us(39ns) 270us(39ns) 274us(39ns) 2000 741us(48ns) 740us(48ns) 743us(48ns) 3000 1004us(41ns) 1008us(41ns) 1014us(42ns) 4000 1216us(36ns) 1229us(37ns) 1270us(38ns) 5000 1669us(39ns) 1672us(39ns) 1717us(40ns) 6000 2220us(42ns) 2217us(42ns) 2257us(43ns) 7000 2711us(43ns) 2707us(43ns) 2786us(44ns) 8000 3232us(44ns) 3227us(44ns) 3308us(46ns) 9000 3567us(43ns) 3593us(43ns) 3652us(44ns) _______________________________________________ QL-Users Mailing List http://www.q-v-d.demon.co.uk/smsqe.htm
