Merge Sort HW

[eshaank1]

Task 1:
Merge Sort is a sorting algorithm that works by splitting an array into smaller subarrays and then sorting them and then merging them back together in order. The sorting algorihm divides the array in half durting each step, leading to a recursion depth of log n. Each level of recursion requires merging, which takes O(n) operations. So the total time complexity is O(n log n). Bubble Sort has a worst-case time complexity of O(n²), because it repeatedly swaps side by side elements, and it is inefficient for large datasets compared to merge sort. Quick sort is usually faster than merge sort but has a worst case complexity of O(n squared) if the starting point is chosen badly, and it sorts in place unlike merge sort.

Task 2:
Option A

public class IterativeMergeSort {
    public static void mergeSort(int[] arr) {
        int n = arr.length;
        int[] temp = new int[n];

        for (int size = 1; size < n; size *= 2) {
            for (int leftStart = 0; leftStart < n - 1; leftStart += 2 * size) {
                int mid = Math.min(leftStart + size - 1, n - 1);
                int rightEnd = Math.min(leftStart + 2 * size - 1, n - 1);
                merge(arr, temp, leftStart, mid, rightEnd);
            }
        }
    }

    private static void merge(int[] arr, int[] temp, int leftStart, int mid, int rightEnd) {
        int left = leftStart, right = mid + 1, index = leftStart;

        while (left <= mid && right <= rightEnd) {
            if (arr[left] <= arr[right]) {
                temp[index++] = arr[left++];
            } else {
                temp[index++] = arr[right++];
            }
        }

        while (left <= mid) {
            temp[index++] = arr[left++];
        }

        while (right <= rightEnd) {
            temp[index++] = arr[right++];
        }

        for (int i = leftStart; i <= rightEnd; i++) {
            arr[i] = temp[i];
        }
    }

    public static void main(String[] args) {
        int[] arr = {38, 27, 43, 3, 9, 82, 10};
        mergeSort(arr);
        System.out.println("Sorted array: " + Arrays.toString(arr));
    }
}