1. Sorting Algorithms

a. Merge Sort

How it works:

1. Divide the array into two halves.
2. Recursively sort each half.
3. Merge the sorted halves into one sorted array.

Time complexity:

• Best: O(n log n)
• Average: O(n log n)
• Worst: O(n log n)

Space complexity: O(n) (uses extra space for temporary arrays)

Java code:

void mergeSort(int[] arr, int l, int r) {
    if (l < r) {
        int mid = l + (r - l) / 2;
        mergeSort(arr, l, mid);
        mergeSort(arr, mid + 1, r);
        merge(arr, l, mid, r);
    }
}

void merge(int[] arr, int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;

    int[] left = new int[n1];
    int[] right = new int[n2];

    for (int i = 0; i < n1; i++)
        left[i] = arr[l + i];
    for (int j = 0; j < n2; j++)
        right[j] = arr[m + 1 + j];

    int i = 0, j = 0, k = l;
    while (i < n1 && j < n2) {
        if (left[i] <= right[j])
            arr[k++] = left[i++];
        else
            arr[k++] = right[j++];
    }

    while (i < n1) arr[k++] = left[i++];
    while (j < n2) arr[k++] = right[j++];
}

b. Quick Sort

How it works:

1. Choose a pivot element (e.g. last element).
2. Partition array so that:
   • Left of pivot: elements ≤ pivot
   • Right of pivot: elements > pivot
3. Recursively apply the above steps to left and right partitions.

Time complexity: