Mergesort and Quicksort

class Merge implements Merging { public int[] merge (int[] B, int[] C) {

} public void choice (int c) {} }Assume that the arrays

trace Merge.java array=16,46,46,46,61,78,89,91 array2=27,34,37,56,75,81,83,95These arrays are already sorted, so the precondition for merge is satisfied, and you should get a sorted result. Test the situations where

class Mergesort implements Sorting { public int[ ] sort (int[ ] A) { int size = A.length;

} // access to merge(B,C) private Merging merger; // this is for the hybrid algorithm (Section 6) private int cutoff=0; public void cutoff (int n) { cutoff=n; } private Sorting insertion_sorter; public void choice (int c) {} public Mergesort() { merger = new TestMerge(); // or Merge() to use your own insertion_sorter = new Insertion(); } }Begin by finding the midpoint:

int mid = size/2;Assign this

run Mergesort.java array=16,46,46,46,61,78,89,91,27,34,37,56,75,81,83,95There is a

run Mergesort.java size=1000000 thread=no check Mergesort.java sizes=200000,500000,1000000 maxtime=60Because of the allocation of scratch space within the recursive calls, you will not be able to run this for very large arrays: 1,000,000 may be the largest that the JAVA run time system allows. Does it make any difference to the performance of merge sort if you give it already-sorted data?

Trace.printmerge (int[] A, int indent, int level, boolean direction);The

public int[] sort (int[] A) { return mergesort (A, 0, 0); } private int[] mergesort (int[] A, int indent, int level) { /* your original code for sort(A) */ }and replace

mergesort (B, new_indent, level+1);and similarly

class Quicksort implements Sorting { public int[ ] sort (int[ ] A) { return quicksort (A, 0, A.length); } private int[ ] quicksort (int[ ] A, int left, int right) {

} // access to split (A, left, right) private Splitting splitter; // this is for the hybrid algorithm private int cutoff=0; public void cutoff (int n) { cutoff=n; } public void choice (int c) {} public Quicksort() { splitter = new TestSplit(); // or Split() to use your own }

Trace.printquick (A, left, right, level, direction)As you did with

trace quick-sort pivot=firstOther ways of choosing the pivot are

run quick-sort sawtoothpc=50to see what I mean by a

trace quick-sort sawtooth=1 pivot=median3and guess what the result of

for (int frag_len = 1; frag_len < size; frag_len *= 2) { for (int from = 0; from < size; from += 2 * frag_len) { // merge B[from...from+frag_len-1] and B[to...to+frag_len-1] // to corresponding segment in A } }When you've done each merge, you can either copy it back, or alternately merge from

This is
`www.PaulTaylor.EU/algorithms/merge+quick.html`
and it was derived from `algorithms/merge+quick.tex`
which was last modified on 21 July 2007.