Merge Sort Simulation - Part 1: General Concept

Merge Sort is a divide and conquer algorithm that splits a list into smaller sublists, sorts those sublists, and then merges them back together to form the sorted list. It is particularly efficient for large datasets.

Steps of Merge Sort:

  1. Divide: Recursively split the list into two halves until each sublist contains a single element or is empty.
  2. Conquer: Sort each of the smaller sublists.
  3. Combine: Merge the sorted sublists back together to form the final sorted list.

alt text

Time Complexity of Merge Sort

Merge Sort has a predictable time complexity due to its divide-and-conquer approach. Here’s a breakdown:

  1. Divide Step: The list is divided into two halves recursively. This takes O(n log n)time because the list is halved at each level of recursion.

  2. Merge Step: At each level of recursion, the merging of two halves takes O(n) time, where n is the number of elements being merged.

  3. Overall Complexity: Since there are O(log n) levels of recursion and each level takes O(n) time to merge, the total time complexity is: O(n log n)

Popcorn Hack

  • Why do we divide the array into halves in Merge Sort?
  • Why does Merge Sort have O(n log n) complexity?

Example Walk Through

public class MergeSort {

    // Main function to sort an array
    public static void mergeSort(int[] array) {
        if (array.length < 2) {
            return; // Base case: an array of length 0 or 1 is already sorted
        }
        
        // Find the middle index
        int mid = array.length / 2;

        // Divide the array into two halves
        int[] left = new int[mid];
        int[] right = new int[array.length - mid];

        // Copy data to left and right subarrays
        System.arraycopy(array, 0, left, 0, mid);
        System.arraycopy(array, mid, right, 0, array.length - mid);

        // Recursively sort both halves
        mergeSort(left);
        mergeSort(right);

        // Merge the sorted halves
        merge(array, left, right);
    }

    // Helper function to merge two sorted arrays
    public static void merge(int[] array, int[] left, int[] right) {
        int i = 0, j = 0, k = 0;

        // Merge the two sorted subarrays
        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) {
                array[k] = left[i];
                i++;
            } else {
                array[k] = right[j];
                j++;
            }
            k++;
        }

        // Copy the remaining elements of left[] if any
        while (i < left.length) {
            array[k] = left[i];
            i++;
            k++;
        }

        // Copy the remaining elements of right[] if any
        while (j < right.length) {
            array[k] = right[j];
            j++;
            k++;
        }
    }

    // Main method to test the merge sort
    public static void main(String[] args) {
        int[] array = { 38, 27, 43, 3, 9, 82, 10 };
        System.out.println("Original array:");
        System.out.println(Arrays.toString(array));

        mergeSort(array);

        System.out.println("Sorted array:");
        System.out.println(Arrays.toString(array));
    }
}

Explanation of the Code:

  1. mergeSort function:
    • This function is the main sorting function.
    • If the array has only one element or is empty, it’s already sorted, and the function returns immediately.
    • Otherwise, the array is split into two subarrays: left and right.
    • It recursively sorts each half using the same mergeSort function.
  2. merge function:
    • After both halves are sorted, we need to combine them back together in sorted order.
    • It compares the elements of left and right arrays, putting the smaller element into the main array until one of the subarrays is exhausted.
    • After that, it copies any remaining elements from the left or right arrays into the main array.
  3. main function:
    • This function tests the merge sort by creating an unsorted array, printing it, sorting it using mergeSort, and then printing the sorted array.

Let’s say we have this array:

[38, 27, 43, 3, 9, 82, 10]

  1. Divide Step:
    • Split into two parts:
      Left: [38, 27, 43]
      Right: [3, 9, 82, 10]
  2. Recursion:
    • Sort each half:
      • Left: [38, 27, 43] → Split again into [38] and [27, 43] → Sort to [27, 38, 43]
      • Right: [3, 9, 82, 10] → Split into [3, 9] and [82, 10] → Sort to [3, 9] and [10, 82]
  3. Merge Step:
    • Now merge back:
      • Merging [27, 38, 43] and [3, 9, 10, 82], results in the sorted array:
        [3, 9, 10, 27, 38, 43, 82]
class MergeSort {
    void merge(int arr[], int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;

        int L[] = new int[n1];
        int R[] = new int[n2];

        for (int i = 0; i < n1; i++)
            L[i] = arr[left + i];
        for (int j = 0; j < n2; j++)
            R[j] = arr[mid + 1 + j];

        int i = 0, j = 0, k = left;
        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++;
        }
    }

    void sort(int arr[], int left, int right) {
        if (left < right) {
            int mid = left + (right - left) / 2;

            sort(arr, left, mid);
            sort(arr, mid + 1, right);
            merge(arr, left, mid, right);
        }
    }

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

    public static void main(String args[]) {
        int arr[] = { 12, 11, 13, 5, 6, 7 };
        MergeSort ob = new MergeSort();
        ob.sort(arr, 0, arr.length - 1);
        System.out.println("Sorted array:");
        printArray(arr);
    }
}

Popcorn hack modifications to this code

  • ask class to modify the code to sort the array in decesnding order
  • Ask students to count the number of comparisons happening in the merge() function and print the count.
  • Write a Java method that checks if a given array is already sorted before applying Merge Sort.

Homework

Task 1:

  1. Explain Merge Sort in Your Own Words Write a short explanation (100-200 words) describing:
  • How Merge Sort works.
  • Why it has O(n log n) complexity.
  • How it differs from other sorting algorithms like Bubble Sort or Quick Sort.

Task 2

  1. Code a Modified Version of Merge Sort Choose ONE of the following modifications and implement it in Java:
  • Option A: Merge Sort Without Recursion
    • Modify the Merge Sort algorithm to work iteratively instead of recursively.
  • Option B: Counting Inversions Using Merge Sort
    • Modify Merge Sort to count the number of inversions in an array. (An inversion is when a larger number appears before a smaller number in an array.)
  • Option C: Sorting a Linked List Using Merge Sort
    • Instead of an array, implement Merge Sort for a singly linked list.