CS 2401 Assignment #3

Due Date: Monday, February 15, 2010, or Tuesday, February 16, 2010, depending on the day of your lab.

Objective: The goal of this assignment is to practice recursion.

Problem to solve: Often, we need to sort ("order") elements of the array in order (e.g., in alphabetic order). For example, we can sort students by their last names, sort prices from cheapest to highest, etc. For example, if we start with an array

 3 1 -5 0 2 6 4
we want to sort it, i.e., produce a sorted array
 -5 0 1 2 3 4 6

Method: One of the fastest methods for sorting is called mergesort. We will study this method later in detail, right now, we just want you to implement this method.

Mergesort: main idea. The mergesort method is as follows.

Example. For example, if we start with an array

 3 1 -5 0 2 6 4
of size s = 7, we take, as the 1st half-array, an array consisting of the first 7/2 = 3 elements
 3 1 -5
and as a 2nd half-array, the array consisting of all the remaining elements
 0 2 6 4

Method (cont-d). We sort each half-array by using the same mergesort algorithm (this is recursion, after all).

Example: In the above example, the 1st half-array becomes

 -5 1 3
and the 2nd half-array becomes
 0 2 4 6

Method (cont-d). After this, we "merge" these two sorted half-arrays into a new array by using the following procedure.

We keep track of the locations of the first unprocessed element in both half-arrays. In the beginning, these are locations #0 in the 1st half-array and #0 in the 2nd half-array.

Example. In the above example, the corresponding elements are marked here:

 _-5_ 1 3;   _0_ 2 4 6

Method (cont-d). We compare the corresponding elements of the two half-arrays and place the smallest of these two elements into the new array.

Example: At first, we compare -5 and 0, the smallest is -5, so we place it into the new array:

 -5 ? ? ? ? ? ?
and increase the location of the 1st unprocessed element of the 1st half-array by 1:
 -5 _1_ 3;   _0_ 2 4 6
Then, we again compare the first unprocessed elements, this time they are 1 and 0. The smallest of these two elements is 0, so we place 0 into the new array:
 -5 0 ? ? ? ? ?
Since this 0 came from the 2nd array, we increase the location of the 1st unprocessed element of the 2nd half-array by 1.
 -5 _1_ 3;   0 _2_ 4 6
Again we compare the elements corresponding to first unprocessed locations in both half-arrays. These times, these elements are 1 and 2. 1 is smaller, so we place it into the new array:
 -5 0 1 ? ? ? ?
 
Now, first unprocessed elements are:
 -5 1 _3_;   0 _2_ 4 6
The smallest of 2 and 3 is 2, so we place 2 into the new array:
 -5 0 1 2 ? ? ?
The marked elements are now 3 and 4:
 -5 1 _3_;   0 2 _4_ 6
3 is smaller, so we place it into the new array:
 -5 0 1 2 3 ? ?
Now, all the elements in the 1st half-array are processed, so the first unprocessed location is outside the 1st half-array scope:
 -5 1 3 _ _;   0 2 _4_ 6
Since there are no elements in the 1st half-array left to compare, we simply move marked elements from the 2nd half-array into the new array, one by one. First, we move 4, resulting in
 -5 0 1 2 3 4 ?
and
 -5 1 3 _ _;   0 2 4 _6_
Then, we move the element 6, resulting in
 -5 0 1 2 3 4 6
and
 -5 1 3 _ _;   0 2 4 6 _ _
In both half-arrays, there are now no elements left to compare, so we stop and return the resulting sorted array
 -5 0 1 2 3 4 6

Assignment: Write a program that implements mergesort.