I have made some modifications to my sorting algorithm which has has increased the speed some what.
The high-level sorting algorithm:
1. iterate over the input array identifying the runs of in-order objects
2. while we have more than 1 run goto 3 else goto 11
3. iterate over the runs comparing the "first" object of each run to identify the run which has the next sorted object making note of the previously selected run.
4. if the selected run's "last" object is greater than or equal to the previously selected run's "first" object then we can assume that the entire selected run can be added to the sorted output array. goto 5 else goto 6
5. copy all the objects in the selected run into the sorted output array. goto 7
6. copy only the "first" object in the selected run into the sorted output array.
7. remove the "first" object from the selected run.
8. if the selected run has no more objects then goto 9 else 10
9. remove the selected run from the list of runs
10. goto 2
11. there is only one run and so directly copy the run into sorted output array.
12. return the sorted array.
I have made a little benchmark on typical data sets generated from my actual compressor (well converted to integers) and it is pretty pretty good.
The jar file and data sets can be found here:
http://javaunlimited.net/hosted/moogie/benchmark.zip (i hope Woogley is ok with that)
The test was on a P4 3Ghz dual core running windows XP with
java version "1.5.0_02"
Java(TM) 2 Runtime Environment, Standard Edition (build 1.5.0_02-b09)
Java HotSpot(TM) Client VM (build 1.5.0_02-b09, mixed mode)
- The wikicompress.RunSort.sort1() resuses the same temporary array each sort.
- each sort algorithm was performed 1000 times
- the time is in milliseconds
- source code is included in the jar file.
- the gnu.util.arrays.sort is apparently what is used in the GNU java compiler.
Results:
FILE: data_0.txt
java.util.arrays.sort() 359
gnu.java.util.arrays.sort() 547
wikicompress.RunSort.sort() 188
wikicompress.RunSort.sort1() 141
FILE: data_1.txt
java.util.arrays.sort() 391
gnu.java.util.arrays.sort() 532
wikicompress.RunSort.sort() 203
wikicompress.RunSort.sort1() 219
FILE: data_2.txt
java.util.arrays.sort() 359
gnu.java.util.arrays.sort() 485
wikicompress.RunSort.sort() 172
wikicompress.RunSort.sort1() 156
FILE: data_3.txt
java.util.arrays.sort() 453
gnu.java.util.arrays.sort() 516
wikicompress.RunSort.sort() 297
wikicompress.RunSort.sort1() 266
FILE: data_4.txt
java.util.arrays.sort() 375
gnu.java.util.arrays.sort() 531
wikicompress.RunSort.sort() 219
wikicompress.RunSort.sort1() 187
FILE: data_5.txt
java.util.arrays.sort() 375
gnu.java.util.arrays.sort() 500
wikicompress.RunSort.sort() 188
wikicompress.RunSort.sort1() 156
FILE: data_6.txt
java.util.arrays.sort() 391
gnu.java.util.arrays.sort() 516
wikicompress.RunSort.sort() 203
wikicompress.RunSort.sort1() 156
FILE: data_7.txt
java.util.arrays.sort() 579
gnu.java.util.arrays.sort() 625
wikicompress.RunSort.sort() 187
wikicompress.RunSort.sort1() 157
FILE: data_8.txt
java.util.arrays.sort() 344
gnu.java.util.arrays.sort() 469
wikicompress.RunSort.sort() 203
wikicompress.RunSort.sort1() 141
FILE: data_9.txt
java.util.arrays.sort() 563
gnu.java.util.arrays.sort() 594
wikicompress.RunSort.sort() 172
wikicompress.RunSort.sort1() 156
FILE: data_10.txt
java.util.arrays.sort() 532
gnu.java.util.arrays.sort() 563
wikicompress.RunSort.sort() 172
wikicompress.RunSort.sort1() 140
FILE: data_11.txt
java.util.arrays.sort() 453
gnu.java.util.arrays.sort() 579
wikicompress.RunSort.sort() 297
wikicompress.RunSort.sort1() 250
FILE: data_12.txt
java.util.arrays.sort() 343
gnu.java.util.arrays.sort() 485
wikicompress.RunSort.sort() 172
wikicompress.RunSort.sort1() 141
FILE: data_13.txt
java.util.arrays.sort() 359
gnu.java.util.arrays.sort() 469
wikicompress.RunSort.sort() 156
wikicompress.RunSort.sort1() 125
FILE: data_14.txt
java.util.arrays.sort() 406
gnu.java.util.arrays.sort() 532
wikicompress.RunSort.sort() 187
wikicompress.RunSort.sort1() 141
FILE: data_15.txt
java.util.arrays.sort() 438
gnu.java.util.arrays.sort() 531
wikicompress.RunSort.sort() 313
wikicompress.RunSort.sort1() 281
FILE: data_16.txt
java.util.arrays.sort() 375
gnu.java.util.arrays.sort() 485
wikicompress.RunSort.sort() 187
wikicompress.RunSort.sort1() 141
FILE: data_17.txt
java.util.arrays.sort() 344
gnu.java.util.arrays.sort() 469
wikicompress.RunSort.sort() 172
wikicompress.RunSort.sort1() 156
FILE: data_18.txt
java.util.arrays.sort() 328
gnu.java.util.arrays.sort() 469
wikicompress.RunSort.sort() 188
wikicompress.RunSort.sort1() 140
FILE: data_19.txt
java.util.arrays.sort() 469
gnu.java.util.arrays.sort() 501
wikicompress.RunSort.sort() 265
wikicompress.RunSort.sort1() 203
FILE: data_20.txt
java.util.arrays.sort() 422
gnu.java.util.arrays.sort() 516
wikicompress.RunSort.sort() 235
wikicompress.RunSort.sort1() 203
FILE: data_21.txt
java.util.arrays.sort() 343
gnu.java.util.arrays.sort() 485
wikicompress.RunSort.sort() 172
wikicompress.RunSort.sort1() 125
FILE: data_22.txt
java.util.arrays.sort() 344
gnu.java.util.arrays.sort() 453
wikicompress.RunSort.sort() 204
wikicompress.RunSort.sort1() 156
FILE: data_23.txt
java.util.arrays.sort() 328
gnu.java.util.arrays.sort() 453
wikicompress.RunSort.sort() 157
wikicompress.RunSort.sort1() 140
FILE: data_24.txt
java.util.arrays.sort() 516
gnu.java.util.arrays.sort() 610
wikicompress.RunSort.sort() 187
wikicompress.RunSort.sort1() 141