Popcorn Hack

public class MergeSort {
    public static int[] mergeArrays(int[] array1, int[] array2) {
        // get lengths
        int array1Length = array1.length;
        int array2Length = array2.length;
        int[] merged = new int[array1Length + array2Length];

        // tracking vars
        int i = 0, j = 0, k = 0;

        // first merge the ararys in order
        while (i < array1Length && j < array2Length) {
            if (array1[i] <= array2[j]) {
                merged[k] = array1[i];
                i++;
            }
            else {
                merged[k] = array2[j];
                j++;
            }
            k++;
        }

        // copy remaining array 1 stuff
        while (i < array1Length) {
            merged[k] = array1[i];
            i++;
            k++;
        }

        // copy remaining array 2 stuff
        while (j < array2Length) {
            merged[k] = array2[j];
            j++;
            k++;
        }

        return merged;
    }

    public static void main(String[] args) {
        // make arrays
        int[] array1 = {1, 3, 5, 7};
        int[] array2 = {2, 4, 6, 8};

        // merge the stuff
        int[] merged = mergeArrays(array1, array2);

        System.out.println("Merged array:");
        for (int i : merged) {
            System.out.print(i + " ");
        }
    }
}

MergeSort.main(new String[0]);

Merged array:
1 2 3 4 5 6 7 8

1. Time Complexity of Merge Sort:

Merge Sort has a time complexity of O(n log n) in all cases (best, average, and worst). This is because the algorithm divides the input array into halves recursively (logarithmic depth) and then merges the sorted halves (linear work per level). The division and merging steps together result in the efficient O(n log n) complexity.

2. Comparison with Bubble Sort and Quicksort:

  • Bubble Sort: Bubble Sort has a time complexity of O(n²) in the worst and average cases, making it much slower than Merge Sort for large datasets. It repeatedly compares adjacent elements and swaps them if necessary, which is inefficient.
  • Quicksort: Quicksort has an average time complexity of O(n log n), similar to Merge Sort. However, its worst-case complexity is O(n²) if the pivot selection is poor. Merge Sort is more predictable in performance, while Quicksort is generally faster due to lower constant factors.

3. Why Merge Sort is a “Divide and Conquer” Algorithm:

Merge Sort is a “divide and conquer” algorithm because it divides the problem into smaller subproblems, solves each subproblem independently, and then combines the solutions. Specifically, it splits the array into two halves, recursively sorts each half, and merges the sorted halves into a single sorted array. This approach ensures efficient sorting by breaking the problem into manageable parts.

4. Stability of Merge Sort:

Merge Sort is a stable sorting algorithm, meaning it preserves the relative order of equal elements in the input array. During the merging step, if two elements are equal, the one from the left subarray is placed before the one from the right subarray, ensuring stability. This property makes Merge Sort suitable for applications where maintaining the order of equivalent elements is important.

HW

public class MergeSort {

    // function to merge two subarrays
    private static void merge(int[] array, int left, int mid, int right) {
        int[] leftArray = new int[mid - left + 1];
        int[] rightArray = new int[right - mid];

        // copy data to temp arrays
        System.arraycopy(array, left, leftArray, 0, leftArray.length);
        System.arraycopy(array, mid + 1, rightArray, 0, rightArray.length);

        int i = 0, j = 0, k = left;

        // merge the temp arrays back into the original array
        while (i < leftArray.length && j < rightArray.length) {
            array[k++] = (leftArray[i] <= rightArray[j]) ? leftArray[i++] : rightArray[j++];
        }

        // copy remaining elements, if any
        while (i < leftArray.length) {
            array[k++] = leftArray[i++];
        }
        while (j < rightArray.length) {
            array[k++] = rightArray[j++];
        }
    }

    // recursive function to perform merge sort
    public static void mergeSort(int[] array, int left, int right) {
        if (left < right) {
            int mid = left + (right - left) / 2;

            mergeSort(array, left, mid);
            mergeSort(array, mid + 1, right);

            merge(array, left, mid, right);
        }
    }

    // main method to test the merge sort implementation
    public static void main(String[] args) {
        int[] array = {12, 11, 13, 5, 6, 7};
        System.out.println("original array:");
        System.out.println(java.util.Arrays.toString(array));

        mergeSort(array, 0, array.length - 1);

        System.out.println("sorted array:");
        System.out.println(java.util.Arrays.toString(array));
    }
}

MergeSort.main(new String[0]);