a) Trace bottom-up merge sort with the following input. Each merge result row should have the merging result from the previous step, and the last row should contain the final sorted result. Index 0 Input75 89 11 83 12 6 Merge Result Merge Result Merge Result Merge Result 3 4 7 13 53 27 96 b) Show the partition result of this input array using the algorithm provided Provide array contents after each swap (including the final swap). If there are multiple swaps, provide a row for each swap Index Input wa with ? 0 25 15 84 57 24 65 1 4 16 26 83 Algorithm for b. / Partition into a[lo..j-1, atj, atj+1hi] private int partition (T[ a, int lo, int hi) inti-lo, j-hi 1: 17 left and right scan indices T v = a [101: // the pivot while (true17 scan right, scan left, check for scan complete, and exchange while (Sortutils.isLessThan (a++i, v) //++i is evaluated to i+1 if (is-hi) { break; 10 while (Sortutils.isLessThan (v, aj)) /7--j is evaluated to j-1 12 13 14 15 16 17 18 19 20 21 if j1o) break: if (i j) t break SortUtils.swap (a, i, j) Sortutils.swap (a, lo, j) // Put the pivot into position return j; // with a[1o..j-1