CS 216, Lab #11
Due as specified on course webpage
quests/merge.c -- merge 2 arrays in order
quests/merge3.c -- merge 3 arrays in order --
by calling merge twice, and free(the result of the first merge), for
bonus marks.
Two integer arrays that are in ascending order need to be
merged, the result array should have all the elements of both,
still in ascending order.
This function forms the basis of the (maximally efficient)
O(n lg n) merge-sort: Break a list into halves, merge-sort each
half, and then merge the halves. Of course, this requires that
merge be done intelligently, so it is O(n). Do not throw away the ordering
by doing something stupid like concatenating the the two arrays
and then bubble sorting, for instance!
Once it works for the test case, test it with mipsmark and submit
with submit cs216.
The way you declare a function with arguments, in this case, is:
int* merge (const int a[], int alen, const int b[], int blen) // OR
int* merge (const int* a, int alen, const int* b, int blen)
Either way, a and b are pointers to the start of each
array. a[0] and *a mean the same value, etc.
Instructions: May
I remind you that ALL programs MUST be well commented!!!!
-
merge must allocate enough space on the heap (using malloc())
to hold the merged array,
- malloc returns a pointer to this space (on the "heap").
It is this pointer that YOU return from your merge function.
Remember that
integers are stored in sizeof(int) bytes, which is usually
4. (You can always find the size of a type by using sizeof(). )
- ... so you will need (alen + blen)*sizeof(int) bytes.
- The function that called you will be responsible to free() this space (using your pointer)
-
for merge3.c, also write a function whose arguments are 3
arrays, merge two, merge in the third, and then free (dispose of) the
result of the first merge.
Follow the instructions for Lab 2. You must
debug and test your code using gcc merge.c, and then pass the test cases:
mipsmark merge.c
Be sure your name is
included
as a comment, and submit a copy of the file using submit cs216 merge.c.
If you have trouble with mipsmark, check the validity of your
calculations.
Then see common reasons mipsmark may
fail.
compile with gcc:
gcc merge.c
there will be either syntax errors to correct, or
The executable file a.out
Run it with the command ./a.out
Or else, if you don't like
the default name
gcc -o merge merge.c
./merge
Only note that the syntax for declaring argument types for functions
is archaic.
Lin Jensen,