Consider the modified quicksort, called quicksort2. The only modification is that if a portion of an array is already sorted then it won't recurse. Prove that the time complexity for quicksort2 is O(n²). You may assume the partition function selects the pivot in O(n) time.

= void quicksort2(int[] a, int left, int right) { if (left a[i+1]) { return false; } } return true; ; }