Courses‎ > ‎APCS - Term 1‎ > ‎Konstantinovich‎ > ‎

2019-03-15 Mergesort

posted Mar 15, 2019, 5:41 AM by Konstantinovich Samuel   [ updated Mar 15, 2019, 8:03 AM ]
Deadline Wednesday March 20th
(Monday is a guaranteed lab day)

Git repo:
MKS22X-merge

File:
Merge.java

One public method:
/*sort the array from least to greatest value. This is a wrapper function*/
public static void mergesort(int[]data){}


Pseudocode:
mergesort(data,lo,hi):
  if lo >= hi : 
    return 
  mergesort left side
  mergesort right side
  merge

You can make arrays as temporary space if you wish! This is the easier method, but will be a bit slower.

If you want to make it faster:
Have your mergesort take both the data and temp arrays. Mergesort the temp, and merge into the original!
e.g.
    private static void mergesort(int[]data, int[]temp, int lo, int hi){}
Pre-allocate a temp array in your mergesort wrapper method, and copy the data into it.



Sample speeds of mergesort WITH creating many arrays at each level (not optimized)
Array size	Value Range	merge/builtin ratio 
31250		1000000000	0.8554216867469879
125000		1000000000	1.421487603305785
500000		1000000000	1.657314629258517
2000000		1000000000	1.924944812362031
31250		10	        3.25
125000		10	        6.15
500000		10	        6.45
2000000		10	        6.880503144654088

Optimized: (using one temp array the whole time)
Size Max Value merge/builtin ratio
31250 1000000000 0.804
125000 1000000000 1.024
500000 1000000000 1.198
2000000 1000000000 1.443
31250 10         3.0
125000 10         4.0
500000 10         4.164
2000000 10         4.277

Comments