Merge Sort and Insertion Sort Programs

In C++

Implement merge sort and insertion sort to sort an array/vector of integers. Name one program mergesort and the other insertsort. Your programs should be able to read inputs from a file called data.txt where the first value of each line is the number of integers that need to be sorted, followed by the integers.

Example values for data.txt:

3 18 1 5 12

8 3 3 5 4 6 6 2 2

The output will be written to files called merge.out and insert.out. For the above example the output would be:

1 3 5 12 18

2 2 3 3 4 5 6 6 8

```````````````````````````````````````````````````

Please fix the code below:

Insertion Sort

//Description: Take an input file and use insertion sort to sort // and place in an output file

#include #include #include

using namespace std;

void insertion_sort(int arr[], int x) //function that uses insertion sort { int key; int i; int j;

for(i = 1; i < x; i++){ key = arr[i]; j = i - 1;

/*Elements moved into the array that are *greater than key to a position one position ahead *of current position*/

while(j >= 0 && arr[j] > key){ arr[j+1] = arr[j]; j = j - 1; }

arr[j + 1] = key; } }

int main() { ifstream in("data.txt"); if(in.fail()){ cout << "Error: File did not open" << endl; return 0; }

ofstream out("insert.out");

int x;

//read in size of the array while(in >> x){ int *arr = new int[x]; int j = 0; while(j < x){ in >> arr[j]; j++; } //call insert sort function insertion_sort(arr, x);

//write to the ouput file for(int i; i < x; i++){ out<

in.close(); out.close(); cout<<"Data has been sorted and place in file insert.out" << endl;

return 0; }

Merge Sort

//Description: This program is to use merge sort to sort an undetermined amount of // numbers from a file, sort them and output in new file

#include #include #include

using namespace std;

/*Function splits the merge sort in to half*/ void merge(int *a, int bottom, int top, int middle){ int i = bottom; int j = middle + 1; int k = 0; int temp[top - bottom + 1];

//Merges parts into temp[] while(i <= middle && j <= top){ if(a[i] , a[j]){ temp[k] = a[i]; k++; i++; } else{ temp[k] = a[j]; k++; j++; } } //place ramining values from bottom to middle in sorted array while(i <= middle){ temp[k] = a[i]; k++; i++; }

//place ramaining values from middle+1 to top in sorted array while(j <= top){ temp[k] = a[j]; k++; j++; }

//move sorted array from temp to official array for(i = bottom; i <= top; i++){ a[i] = temp[i - bottom]; } }

/*splits array recursively down to signle units*/ void merge_sort(int *a, int bottom, int top){ int middle;

if(bottom < top){ middle = (bottom + top)/2;

//split in half merge_sort(a, bottom, middle); merge_sort(a, middle + 1, top);

//merges everything back together merge(a, bottom, top, middle); } }

int main() { ifstream in("data.txt"); if(in.fail()){ cout << "Error: File did not open" << endl; return 0; }

ofstream out("merge.out");

int x;

//read in size of the array while(in >> x){ int *arr = new int[x]; int j = 0; while(j < x){ in >> arr[j]; j++; } //call insert sort function merge_sort(arr, 0, x - 1); //write to the ouput file for(int i; i < x; i++){ out<