Shown below is the code for the bubble sort consisting of two recursive methods that replace the two nested loops that would be used in its iterative counterpart:

void bubbleSort(int array[])

{ sort(array, 0); }

void sort(int[] array, int i)

{

if (i < array.length - 1) { bubble(array, i, array.length - 1); sort(array, i + 1); }

}

void bubble(int[] array, int i, int j)

{

if (j <= i) return; if (array[j] < array[j - 1])

{ int temp = array[j]; array[j] = array[j - 1]; array[j - 1] = temp; } bubble(array, i, j - 1); }

Draw the recursion tree for bubbleSort when it is called for an array of length 4 with data that represents the worst case. Show the activations of bubbleSort, sort and bubble in the tree. Explain how the recursion tree would be different in the best case.