$ mkdir ~/cs170/labs/lab22 $ cd ~/cs170/labs/lab22
There's one sorting question I tend to hear a lot: "Is there a binary sort?" Well, the idea behind binary search finds its way into two different algorithms. These are Merge Sort and Quick Sort. They both approach the problem the same way as all of our other recursive functions: Break the problem into smaller portions, and build the overall solution from those smaller pieces.
Merge sort is probably the closest to a "binary" sort as you will get. Merge sort simply splits the list into two halves, and recursively calls Merge sort on both halves. Onces it gets the two sorted halves, it simply merges the two together to form a sorted list.
Create a function called void mergeSort(int * aList, int
start, int end)
, which
takes a list of integers, as well as two integers representing the
beginning and end of the portion of the list to be sorted. The end
value is exclusive. This
function should not return anything, it should sort aList
in place. They discussed this modification of the algorithm in the
reading.
int SIZE = 5; int * myList = new int[SIZE]; for(int i = 0; i < SIZE; i++) { myList[i] = SIZE - i; } mergeSort(myList, 0, SIZE); printList(myList); // [1, 2, 3, 4, 5]
The book wrote the entirety of merge sort in one function.
As I showed you today in lecture, it is easier to understand
merge sort if you write one helper function.
You should write a function called merge(int * aList,
int start, int end)
. This function takes a list of integers,
and two integers start and end. It does not
return anything: It sorts the items in place in a_list
You will use start and end to denote the two halves of the list. The middle index of the list denotes the beginning of the second half of the list. All you need to do is to compare the elements at the beginning of each half of the list. If they are out of order, swap them and move on to the next elements. The easiest way to accomplish this is to make a copy of the left and right halves of this list, and place the correct values back into the original list.
One thing you need to be careful about in the merge procedure is that you could easily run out of items in one list before the other. You need to make sure you gracefully handle this situation.
Your mergeSort
function should recursively
call mergeSort on each half of the list, then merge the two
halves together.
The version of merge sort described in the reading and in class today creates two arrays in merge. One to hold the left half, and one to hold the right half. This is easier to reason about what is going on, but does waste space to accomplish.
Modify your merge procedure so that it doesn't create any additional arrays. How much different is your code?