Algorithm to repeatedly divide the array into sub arrays and microsort each. pros. really efficient stable when taking an array with elements of the same value, your sorting them with the same order. o^n LogN fast for large and small arrays

same time complexity as quick sort, but not as good for bubble sort for simpler arrays.

merge sort process

divide the array into two halves
sort each half
merge the two halves back together
repeat until the array is sorted

odd number array for merge sort left side has one more element than right side

popcorn hack write a java program to merge two already sorted arrays into one array

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

        int[] mergedArray = mergeSorting(array1, array2);
        printArray(mergedArray);
    }

    public static int[] mergeSorting(int[] array1, int[] array2) {
        int[] mergedArray = new int[array1.length + array2.length];
        int i = 0, j = 0, k = 0;

        while (i < array1.length && j < array2.length) {
            if (array1[i] <= array2[j]) {
                mergedArray[k++] = array1[i++];
            } else {
                mergedArray[k++] = array2[j++];
            }
        }

        while (i < array1.length) {
            mergedArray[k++] = array1[i++];
        }

        while (j < array2.length) {
            mergedArray[k++] = array2[j++];
        }

        return mergedArray;
    }

    public static void printArray(int[] array) {
        for (int i : array) {
            System.out.print(i + " ");
        }
        System.out.println();
    }
}

MergeSortExample.main(new String[]{});

1 2 3 4 5 6 7 8

HW

Q: What is the time complexity of merge sort in the best, worst, and average cases? Explain why. A: the best case is O(n log n) because it doesnt increase to big over large periods of time

Q: Compare merge sort with bubble sort and quicksort. When might merge sort be preferred? A: merge sort is better for larger arrays while quicksort is faster in smaller arrays.

Q: Why is merge sort considered a “divide and conquer” algorithm? A: because it divides the array into smaller sub arrays and sorts them before merging them back together.

Q: Is merge sort stable? Why does this matter? A: yes, because it keeps the order of the elements with the same value.

Instructions Task: Write a function in Java that implements merge sort.

Bonus task: Modify your merge sort function to count how many comparisons are made during sorting.

public class MergeSort {
    private int comparisonCount = 0; // Variable to count comparisons

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

        MergeSort mergeSort = new MergeSort();
        int[] mergedArray = mergeSort.mergeSorting(array1, array2);
        printArray(mergedArray);
        System.out.println("Total comparisons made: " + mergeSort.comparisonCount);
    }

    public int[] mergeSorting(int[] array1, int[] array2) {
        int[] mergedArray = new int[array1.length + array2.length];
        int i = 0, j = 0, k = 0;

        while (i < array1.length && j < array2.length) {
            comparisonCount++; // Counting each comparison
            if (array1[i] <= array2[j]) {
                mergedArray[k++] = array1[i++];
            } else {
                mergedArray[k++] = array2[j++];
            }
        }

        while (i < array1.length) {
            mergedArray[k++] = array1[i++];
        }

        while (j < array2.length) {
            mergedArray[k++] = array2[j++];
        }
        return mergedArray;
    }

    public static void printArray(int[] array) {
        for (int num : array) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
}

MergeSort.main(new String[]{});

1 2 3 4 5 6 7 8 
Total comparisons made: 7

CSA Merge Sorting

Stuff for Merge sorting

CSA Merge Sorting

HW