Algorithm for b.

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 8911 83 126 Merge Result Merge Result Merge Result Merge Result 3 4 6 13 53 27 96 8 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 Swa with? 0 3 4 24 8 25 1584 65 1 16 26 83 1 2 // Partition into a [lo..j-1], a[J], a[j+1..h] private > int partition (T[] a, int lo, int hi) { int -lo, j = hi + 1; // left and right scan indices T v-a [lol 17 the pivot while (true // Scan right, scan left, check for scan complete, and exchange 4 while (SortUtils.isLessThan (a [++i, v)) t//++i is evaluated to i+1 if (ihi) break 10 at--j])) {//--j is evaluated to j1 while (SortUtils.isLessThan(v, if (j1o) break 12 13 14 15 16 17 18 19 20 21 if (i - j) break SortUtils.swap (a, i, j); SortUtils.swap(a, lo, j); / Put the pivot into position return j; // with a [1o..j-1]