In this lesson…

  1. We’re going to talk specifically about how merge sort works.
  2. Apply recursive algorithms to sort elements of array or Arraylist objects.

Essential Knowledge

Merge sort is a recursive sorting algorithm that can be used to sort elements in an array or Arraylist

Basic of Merge sort

Look at this method called mergeSort where I pass in an array, and then I immediately make a recursive a call to mereSort again with just the left half of my array. And Once I’ve got the left have taken care of, then I make a recursive call to mergeSort with the right half of my array. Then I merge left and right together.

mergeSort(myArray) {
    mergeSort(left);
    mergeSort(right);
    merge(left & right);
}

How sort actually works

mergeSort(myArray, low, high) {
    if (low < high) {
        middle = (high + low)/2;
        mergeSort(myArray, low, middle);
        mergeSort(myArray, middle+1, high);
        merge(myArray, low, middle, high);
    }
}

Merge Method —The merge method


// work from left to right in each virtual myArray
// compare elements to return them to the original array in order
int[] myArray = {3, 4, 6, 8, 1, 2, 5, 7}
// think of the temporary array as two virtual arrays
int[] myArray1 = {3, 4, 6, 8};
int[] myArray2 = {1, 2, 5, 7};
// have to throw an exception for the last one to end the code
// if any elements remain in the lower half of the temporary array, return them to the original array
  1. 1 < 3, 1 goes to the first place
  2. 2 < 3, 2 goes to the second place
  3. 3 < 5, 3 goes to the third place

4. 4 < 5, 4 goes to the fourth place

5. 5 < 6, 5 goes to the fifth place

6. 6 < 7, 6 goes to the sixth place

7. 7 < 8, 7 goes tot the seventh place

8. 8 goes to the last place </detail> ## Code Time ```Java public class sort { public static int[] output; public static void __mergeSort(int[] myArray, int left, int right) { if(left < right) { int i; int center = (left + right) / 2; int p = 0; int j = 0; int k = left; __mergeSort(myArray, left, center); __mergeSort(myArray, center + 1, right); for(i = left; i <= center; i++) { output[p++] = myArray[i]; } while (i <= right && j < p) { if (output[j] <= myArray[i]) { myArray[k] = output[j]; j++; } else { myArray[k] = myArray[i]; i++; } k++; } while (j < p) { myArray[k++] = output[j++]; } } } public static void mergeSort(int[] myArray) { output = new int[myArray.length]; __mergeSort(myArray, 0, myArray.length - 1); output = null; } public static void printArray(int[] array) { for(int data: array) { System.out.print(data + " "); } System.out.println(); } public static void main(String[] args) { int[] array = {3, 4, 6, 8, 1, 2, 5, 9}; System.out.println("before"); printArray(array); mergeSort(array); System.out.println("after"); printArray(array); } } sort.main(null); ``` before 3 4 6 8 1 2 5 9 after 1 2 3 4 5 6 8 9 ## Essential Knowledge Merge sort is a recursive sorting algorithm that can be used to sort elements in an array or Arraylist.