To do: September 29
What are the contents of the array after each merge call? Give the parameters of each merge call: merge(nums, first, last)
int[] nums = {8,4,2,6,9,3};
original - 8 4 2 6 9 3
merge 1 -
merge 2 -
merge 3 -
merge 4 -
merge 5 -
To do: September 29
What are the contents of the array after each merge call? Give the parameters of each merge call: merge(nums, first, last)
int[] nums = {8,4,2,6,9,3};
original - 8 4 2 6 9 3
merge 1 - merge(nums,0,1)
merge 2 -
merge 3 -
merge 4 -
merge 5 -
int[] nums = {8,4,2,6,9,3};
�original - 8 4 2 6 9 3
merge 1 - 4 8 2 6 9 3 merge(nums,0,1)
merge 2 - 2 4 8 6 9 3 merge(nums,0,2)
merge 3 - 2 4 8 6 9 3 merge(nums,3,4)
merge 4 - 2 4 8 3 6 9 merge(nums,3,5)
merge 5 - 2 3 4 6 8 9 merge(nums,0,5)
Warm-up: What are the contents of the array after each merge call? Give the parameters of each merge call: merge(nums, first, last)
© A+ Computer Science - www.apluscompsci.com
Merge sort splits the list into smaller sections or subarrays working its way down to subarrays of size 1.
Once the smallest subarrays are reached, the merge method is called to organize the smaller lists.
Merge copies from the subarray to a temp array.
The items are put in the temp array in sorted order.
Merge sort
© A+ Computer Science - www.apluscompsci.com
public static void mergeSort(int[] arr, int first,int last)
{
if ( first < last )
{
int mid = (first + last)/2;
mergeSort( arr, first, mid );
mergeSort( arr, mid+1, last );
merge( arr, first, last );
}
}
public static void merge(int[] arr,int first,int last)
{
int mid = (first+last)/2;
int first1=first, last1=mid, first2=mid+1, int last2=last;
int[] temp = new int[last-first+1];
int index = 0;
// code here to merge 2 smaller sets of ordered numbers into
// 1 larger set of ordered numbers
}
Merge Sort - entire source code on Repl.it Teams and wksht
a) Where is the temporary array instantiated?
b) What is the size of this array?
1 . . 32
1 . . 16
17 . . 32
17 . .25
26 . . 32
1 . . 8
9. . 16
Merge sort
1
2
31
32
...
...
...
...
log n rows
n numbers in each row to merge
Merge sort runtime
The mergeSort has O(nlogn ). If you compare this runtime with quadratic sorting algorithms, you can see it is much more efficient has n grows large.
https://www.desmos.com/calculator/dccyhvaoxq
The mergeSort method alone has O(logn) run time, but cannot be run without the merge method.
The merge method alone has an O(n) run time and can be run without the mergeSort method.
Go over homework
Test on search and sort algorithms next Thursday
© A+ Computer Science - www.apluscompsci.com
Another divide and conquer sort algorithm: Quick sort
goFormative - quick sort algorithm
Compare and contrast merge sort and quick sort.
Similarities:
Differences:
Homework
MC Test on search and sort algorithms next week on Thursday