<s>[INST] import java.util.Arrays;

public class MergeSort {
 
    public static void main(String[] args) {
 
        int[] list = { 5, 2, 8, 12, 3 };
 
        MergeSort ob = new MergeSort();
        ob.sort(list, 0, list.length - 1);
 
        System.out.println("Sorted array is");
        printArray(list);
    }
 
    private static void printArray(int arr[])
    {
        int n = arr.length;
        for (int i = 0; i < n; ++i)
            System.out.print(arr[i] + " ");
        System.out.println();
    }
 
    void sort(int arr[], int l, int r)
    {
        if (l < r) {
            int m = (l+r)/2;
            sort(arr, l, m);
            sort(arr, m+1, r);
            merge(arr, l, m, r);
        }
    }
 
    void merge(int arr[], int l, int m, int r)
    {
        int n1 = m - l + 1;
        int n2 = r - m;
        int L[] = new int[n1];
        int R[] = new int[n2];
        for (int i = 0; i < n1; ++i)
            L[i] = arr[l + i];
        for (int j = 0; j < n2; ++j)
            R[j] = arr[m + 1 + j];
 
        int i = 0, j = 0;
        int k = l;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            }
            else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }
 
        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }
 
        while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }
}

Question 1: Explain how merge sort works.

Answer:

Merge sort is a divide-and-conquer algorithm that works by recursively dividing the input array into two halves until each subarray contains only one element, and then merging these subarrays back together in sorted order.

Here's a step-by-step breakdown of how merge sort works:

1.  **Divide**: If the array has more than one element, divide it into two halves, `left` and `right`.
2.  **Recursion**: Recursively call the merge sort function on the `left` and `right` subarrays.
3.  **Merge**: Once the `left` and `right` subarrays are sorted, merge them back together in sorted order.

The merge step is where the magic happens. It works by:

*   Creating temporary arrays `L` and `R` to store the `left` and `right` subarrays.
*   Comparing elements from `L` and `R` and placing the smaller element in the original array.
*   Repeating this process until all elements from both subarrays have been merged and placed in the original array in sorted order.

Merge sort has a time complexity of O(n log n), making it one of the most efficient sorting algorithms for large datasets.

Question 2: What is the purpose of creating temporary arrays `L` and `R` in the `merge` function?[/INST]