Can you describe the merge sort algorithm and its time complexity?

Merge sort is a sorting algorithm that follows the divide-and-conquer paradigm. It works by recursively dividing the input array into smaller sub-arrays, sorting them, and then merging them back together to produce a sorted output array.

The merge sort algorithm can be summarized as follows:

• Divide the unsorted array into n sub-arrays, each containing one element.

• Repeat the following steps until there is only one sorted sub-array remaining:

• a. Divide each sub-array into two sub-arrays of roughly equal size.

• b. Sort the two sub-arrays recursively by repeating step 2.

• c. Merge the two sorted sub-arrays into a single sorted sub-array by comparing the elements in each sub-array and inserting them into a new array in sorted order.

• The single sorted sub-array is the final sorted array.

Here is an example implementation of the merge sort algorithm in Java:

public static void mergeSort(int[] arr) {
    if (arr.length > 1) {
        int mid = arr.length / 2;
        int[] left = Arrays.copyOfRange(arr, 0, mid);
        int[] right = Arrays.copyOfRange(arr, mid, arr.length);
        mergeSort(left);
        mergeSort(right);
        merge(arr, left, right);
    }
}

public static void merge(int[] arr, int[] left, int[] right) {
    int i = 0, j = 0, k = 0;
    while (i < left.length && j < right.length) {
        if (left[i] < right[j]) {
            arr[k++] = left[i++];
        } else {
            arr[k++] = right[j++];
        }
    }
    while (i < left.length) {
        arr[k++] = left[i++];
    }
    while (j < right.length) {
        arr[k++] = right[j++];
    }
}

In this implementation, the mergeSort method takes an integer array as input and sorts it using the merge sort algorithm. If the length of the array is greater than 1, it splits the array into two sub-arrays and sorts them recursively using the mergeSort method. It then merges the two sorted sub-arrays using the merge method.

The merge method takes three integer arrays as input: the original array arr and the two sorted sub-arrays left and right. It compares the elements in the two sub-arrays and inserts them into the original array in sorted order.

The time complexity of the merge sort algorithm is O(n log n) in the worst case, where n is the size of the input array. This is because the algorithm divides the input array into two sub-arrays of roughly equal size log n times, and then merges them back together in linear time n times. The merge operation takes O(n) time in the worst case, and it is performed log n times, leading to an overall time complexity of O(n log n).