You are given a list of integers that are not sorted.

Your job is to sort the list in a nondecreasing order.

You should implement four different sorting algorithms.

algorithm 1: choose one of the following: insertion sort, bubble sort, or selection sort

algorithm 2: quick sort

algorithm 3: merge sort

algorithm 4: any algorithm or combination of algorithms you think will run fastest For algorithms 1-3, don’t apply optimization techniques because they are for comparison purposes.

Your task and requirements

(1) You will write a C/C++ program which takes an input file and produces an output file. The input file has the unsorted list of integers, and your output file should be the sorted list. Your list should be non-decreasing: smaller numbers should appear first.

(2) Similar to mp1, your code should build and run on a Linux machine. Make sure you test on the machine before you submit the files.

(3) You should write a Makefile this time too. The TA will build your code by running ‘make’. It should create the necessary binary file.

(4) Your binary file should be named mp2_2023. There should be only a single binary file. It is up to you to make a single or multiple source code files.

(5) Your program should take two command-line arguments:

The first one is the input file name, and the second one is the algorithm index. An example run is:

$ ./mp2_20220001 input00001.txt 2

(6) The input file contains a single line of numbers. An example input file is the following:

10 766020790 1182770779 1333893513 173226398 1071903604 1702255141 2121871803 2124051570 983886268 1364009855

The first number indicates the number of elements in the array. In the above example, there are 10 elements in the list. Note that the first ‘10’ is not a part of the input list.

※ Number of elements in the list will not exceed 1,000,000,000.

※ The integers in the list will be in the range -2,147,483,648 to 2,147,483,647. This is the range of integer that can be represented by the data type int.

(7) Your program should produce an output file. The name of the output file must be “result_algorithm_inputfilename”. In the above example where the input file is “input00001.txt”, the corresponding output file should be named “result_2_input00001.txt”. The output file should have five lines, containing the following items.

1 st line: input file name

2 nd line: algorithm index

3 rd line: input size (the number of elements in the original list)

4 th line: running time in seconds

5 th line: the sorted list

The 5th line does not need to include the input size, because it is there in the 3rd line.

To measure running time, use the clock() function before and after performing the sorting. Your running time does not need to include time used for reading from a file and writing to a file.

In the above example, your output file should be as follows:

input00001.txt

2

10

0.000002

173226398 766020790 983886268 1071903604 1182770779 1333893513 1364009855 1702255141 2121871803 2124051570

(8) It is obvious, but you must NOT use library functions that does the sorting for you. You should implement the sorting algorithms using basic data structures and primitive functions. Your performance should come from your algorithm, not from using optimized libraries or using special hardware such as GPU.

(9) Do not use parallel programming (multiple processes, multiple threads, CUDA, etc.). Implement a single-thread program.

Please write the whole code.