Courses‎ > ‎AP Computer Science 2‎ > ‎Konstantinovich‎ > ‎

2017-03-23 Mergesort

posted Mar 23, 2017, 6:30 AM by Samuel Konstantinovich   [ updated Mar 23, 2017, 11:31 AM ]
We discussed the mergesort yesterday:



def mergesort(ary)  
   mergesort the leftHalf
   mergesort the rightHalf
   mergeTheTwoHalvesIntoTheOriginalArray


This can be done in many ways for example copy each half into a new array:

def mergesort(int[]ary)
  if ...base case...
   stop!
  else
   int[]left = copy of the left side;
   int[]right = copy of the right side;
   mergesort(left)
   mergesort(right)
   mergeTheTwoHalvesIntoTheOriginalArray

This will use more space but is still very fast. This is the easiest way and will be all that I require.

One possible way to make the merge method work well in this situation is to merge directly into the array you want to put the values into (DO NOT return a new array and then copy that over

void merge(int[]a,int[]b,int[]destination){...}
Postcondition:
     destination contains all of the elements of a and b, and is sorted. 
Preconditions:
    a is sorted, b is sorted
    destination.length == a.length + b.length


There are more advanced ways that would be better suited for extra credit. You can think of ways to optimize your mergesort if you feel like entering the merge sort competition which will be put up later.

Write the mergesort in your git directory:
./08*/
  Merge.java
      ->public static void mergesort(int[]ary)
Comments