Question

A4: Merge Sort - Reverse - Due Jul 30, 2020 11:59 PM Summer II 2020 - Data Structures and Algorithms (COSC-2336-01W) void merge (int a[], int aux[], int lo, int mid, int hi) { for (int k = lo; k <= hi; k++) aux[k] = a[k]; int i = lo, j mid+1; for (int k = lo; k <= hi; k++) { if (i > mid) a[k] = aux [j++]; else if (j > hi) a[k] = aux[i++] ; else if (less (aux[j], aux[i])) a[k] = aux[j++] ; else a[k] = aux[i++]; } } The above merge() function sorts values of array (a[]) into an ascending ordered list. Modify this function so that it will generate descending ordered list. PS: Do not submit a new file. Instead, just show in the textbox submission which line should be changed in which way.

Answer 1

We have to change "less(aux[j], aux[i])" to "less(aux[i], aux[j])".

less(aux[j], aux[i]) will return true if aux[j] is less than aux[i], in which case aux[j] will be inserted into the array before aux[i] since it will be in ascending order. Now, if we change it to less(aux[i], aux[j]), it will return true if aux[i] is less than aux[j], or in other words when aux[j] is more than aux[i]. When aux[j] is more aux[i], aux[j] will be inserted into the array. Since the higher values are going into the array before lesser values, it will be in descending order.