Problem Statement

Time Complexity of Sort Function Problem Description What is the time complexity of sort function in the following code: public class Sort { public static void sort(int[] arr, int left, int right) { if (left >= right) return; // Base case: one element int mid = left + (right - left) / 2; sort(arr, left, mid); sort(arr, mid + 1, right); combine(arr, left, mid, right); } private static void combine(int[] arr, int left, int mid, int right) { int[] temp = new int[right - left + 1]; int i = left; // Left subarray pointer int j = mid + 1; // Right subarray pointer int k = 0; // Temp array pointer // Merge in sorted order while (i <= mid && j <= right) { if (arr[i] <= arr[j]) { temp[k++] = arr[i++]; } else { temp[k++] = arr[j++]; } } // Copy remaining elements from left subarray while (i <= mid) { temp[k++] = arr[i++]; } // Copy remaining elements from right subarray while (j <= right) { temp[k++] = arr[j++]; } // Copy combined temp array back to original for (int p = 0; p < temp.length; p++)