$30.00
Description
Goal:
Understanding of merging and mergesort.
Requirements:

Design, code, and test a C program to mergesort a set of intervals of positive rational numbers. The first line of the input will be n, the number of intervals in the remaining n input lines. Each input interval will have four nonzero integer
values: num _ left den _ left num _ right den _ right . If num _ left is positive, then the left end of the interval

is closed at
num _ left
, otherwise the left end of the interval is open at −
num _ left
. Similarly, if
num _ right is
den _ left
den _ left
num _ right
positive, then the right end of the interval is closed at
, otherwise the right end of the interval is open at
den _ right
− ^{num} ^{_} ^{right} . den _ left and den _ right will always be positive, each fraction is in reduced form, and every
den _ right
interval includes at least one number.
The input should be read from standard input (which will be one of 1. keyboard typing, 2. a shell redirect (<) from a file, or 3. cutandpaste. Do NOT prompt for a file name!).
The first line of the output is the number of intervals in the output. Each of the remaining output lines contains four integer values according to the input conventions. In addition to being sorted, adjacent intervals in the output should not overlap or “touch” since your merge routine is expected to clean up such situations. Your code should take Θ(n log n) time.

Submit your C program on Blackboard by 1:45 p.m. on September 21. One of the comment lines should include the compilation command used on OMEGA.
Getting Started: 

1. Sample input: 

5 
( 
2 
, 
19 
) 

2 3 19 3 

3 
3 

7 1 81 10 
( 
7 
, 
81 
] 

1 
10 

1 30 3 4 
[ 
1 
, 
3 
) 

30 
4 

1 50 1 40 
( 
1 
, 
1 
) 

50 
40 

19 3 7 1 
[ 
19 
, 
7 
) 

3 
1 
Sample output: 

3 
( 
1 
, 
1 
) 

1 50 1 40 

50 
40 

1 30 7 1 
[ 
1 
, 
7 
) 

30 
1 

7 1 81 10 
( 
7 
, 
81 
] 

1 
10 

Your program should not use floating point values, i.e. do not use division!

You can get started by using the mergesort code on the course webpage.

All input integers will be in the range 32767 .. 32767, not including 0.