Sorting
Goals
 Practice writing code using linked lists and binary search trees (dynamic structures).
 Practice writing code using recursion.
 Learn to use function addresses (function pointers).
 Learn to use the
qsort(…)
function.  Gain some perspective on different sorting algorithms.
Overview
In this assignment, you will implement the merge sort algorithm for linked lists.
To add some perspective, you will also implement a tree sort (based on
binary search trees) and write a wrapper function for the standard
qsort(…)
function, an implementation of the
quicksort algorithm. However, the main focus on merge sort.
There are no starter files.
About Merge Sort
Recursion is an elegant method for solving many problems. At first it can seem unnatural; however, it is actually very simple once you are used to it. The key thing to understand is that recursive programming has two steps:
 A base case which is trivial.
 A recursive case where you write the solution for the larger case in terms of the solution to smaller cases.
What makes (2) easy is that you simply assume that you have the solution of a smaller case. Life does not generally let you assume you have a solution that you have not yet found; however, if you think about it, it should be obvious (by induction) that recursion works this way.
In this assignment, we will use (1) and (2) above to sort linkedlists of integers using the "mergesort" algorithm. Mergesort is a beautiful algorithm that sorts extremely quickly with large inputs. It is also the best possible algorithm to use for sorting linkedlists.
Merge sort works as follows:

Base case:
You never need to sort a list of length 0 or 1; it is already "sorted", sotospeak. To implement the base case, simply return the input list if its length is 0 or 1. (In general, base cases are trivial like this.) 
Recursive case:
Lets wave our hand, and assume that we know how to sort smaller lists already. (See, recursion is easy.) For the recursive case, we do the following: Divide the list into two smaller lists of equal size, +/ one node.
 Recursively sort each of the two smaller lists. (Wow: easy.)

You now have two small lists that are sorted. To produce the final large
sorted list, you "merge" the two smaller lists together.
 Create a brand new empty list, which will be the resultlist.
 While both small lists are nonempty, look at the head node of each. Take the smaller head node off of the front of its list, and append it to the resultlist.
 Eventually one (or perhaps both) of the smaller lists will be empty. At this stage, append the nonempty list (if there is one) onto the end of the resultlist.
// Credit: Aaron Michaux, Prof. YungHsiang Lu … This description adapted from a previous ECE 264 assignment
Requirements
 Your submission must contain each of the following files, as specified:
 Whenever
size
==0,head
andtail
must be NULL.  Whenever
size
==0,root
must be NULL.  Do not include helpers (if any) here.
 Do not merge sort the array directly. This must use your
merge_sort_list(…)
.  Store the result in the same array that was passed in.

Steps: ① call
create_list(…)
, ② callmerge_sort_list(…)
, ③ store the sorted values inarray
(same memory), ④ callempty_list(…)
.  The purpose is to make
merge_sort_list(…)
comparable with the other sort functions.  This may not result in any heap allocation (i.e., calls to
malloc(…)
), except for the list nodes allocated as a result of callingcreate_list(…)
; those must be freed before this function returns. 
Steps:
① call
create_bst(…)
, ② use inorder traversal to store sorted values inarray
(same memory), ③ callempty_bst(…)
.  Store the result in the same array that was passed in.
 This may not result in any heap allocation (i.e., calls to
malloc(…)
), except for the BST nodes allocated as a result of callingcreate_bst(…)
; those must be freed before this function returns.  This should simply call the
qsort(…)
library function.  The
qsort(…)
function requires the use of function addresses (function pointers).  This may not result in any heap allocation (i.e., calls to
malloc(…)
) by your code.  Yes, this is easy, but make sure you understand how it works!
size
is the number of elements inarray
. When size==0 array must be NULL and vice versa.
 If size==0 then return a list with the head and tail set to NULL.
malloc(…)
may be called from a total of one place in this function and any it depends on. This may not result in any heap allocation (i.e., calls to
malloc(…)
).  Set
head
andtail
to NULL, andsize
to 0. free(…)
may be called from a total of one place in this function and any it depends on.size
is the number of elements inarray
. When size==0 array must be NULL and vice versa.
 If size==0 then return a BST with the root set to NULL.
 This can be a slight modification of your
create_bst_of_int(…)
from the HW11 warmup. malloc(…)
may be called from a total of one place in this function and any it depends on. Set
root
to NULL, andsize
to 0.  This can be a slight modification of
destroy_bst_of_int(…)
from the HW11 warmup. free(…)
may be called from a total of one place in this function and any it depends on. This must cause every line of code in your sorts.c to be executed.
 Every public function in sorts.c must be called directly from
main(…)
and/or from a helper within test_sorts.c.  Use the
typedef
syntax to declare all struct types.  Only the following externally defined functions and constants are allowed in your .c files. (You may put the corresponding #include <…> statements in the .c file or in your sorts.h, at your option.)
header functions/symbols allowed in… stdbool.h bool
,true
,false
sorts.c
,sorts.h
,test_sorts.c
stdio.h printf
,fprintf
,stdout
,FILE
test_sorts.c
stdlib.h malloc
,free
,NULL
,EXIT_SUCCESS
,EXIT_FAILURE
sorts.c
,test_sorts.c
,sorts.h
assert.h assert
sorts.c
,test_sorts.c
 Submissions must meet the code quality standards and the policies on homework and academic integrity.
file  contents  

sorts.h  type definitions 
List
struct type with 3 fields: head (ListNode*), tail (ListNode*) and size (int)

ListNode
struct type with 2 fields: value (int), next (ListNode*)


BST
struct type with 2 fields: root (BSTNode*) and size (int).


BSTNode
struct type with 3 fields: value (int), left , and right (BSTNode*)


function declarations 
one for each required function in your sorts.c


sorts.c  function definitions 
merge sort array(int✶Xarray,Xsize tXsize)
→ return type: void
Sort array using merge_sort_list(…) .

tree sort array(int✶Xarray,Xsize tXsize)
→ return type: void
Sort array by creating a BST and then traversing it.


quick sort array(int✶Xarray,Xsize tXsize)
→ return type: void
Sort array using the qsort(…) standard library function.


create list(constXint✶Xarray,XintXsize)
→ return type: List
Create a new List .


merge sort list(List✶Xlist)
→ return type: void
Merge sort list .


empty list(List✶Xlist)
→ return type: void
Free all the nodes in the list.


create bst(constXint✶Xarray,XintXsize)
→ return type: BST
Create a new BST .


empty bst(BST✶Xbst)
→ return type: void
Free all the nodes in the BST.


test_sorts.c  function definitions 
main(intXargc,Xchar✶Xargv[])
→ return type: int
Test your functions in sorts.c.

expected.txt  functions  Expected output from running your test_sorts.c 
How much work is this?
This is intended to be a similar amount of effort to HW11, but your mileage may vary.
As usual… Programming with dynamic memory usually entails some time debugging. Allow time for that.
Q&A

Can I reuse code from HW11?
Yes. 
Can I add helper functions to sorts.c?
Yes. Make sure the names begin with "_". 
Is there a warmup?
No. 
Is it a violation of the spec if
qsort(…)
callsmalloc(…)
?
No. The only requirement is that your code not callmalloc(…)
as a result of callingquick_sort_array(…)
.
Updates
11/5/2016  Added Q4 and related not to spec under quick_sort_array(…) 
11/6/2016  Change: expected.txt is required 
11/7/2016  Correction: In BST when size ==0 root should be NULL. 
11/13/2016  Added boilerplate reminder about code quality standards and policies. It had been inadvertently omitted. Syllabus already states these apply to every assignment but we try to put a reminder in every assignment. 