Merge Sort Team Teach

By the end of this lesson, you’ll know:

How Merge Sort uses a divide-and-conquer strategy.
Why its time complexity is O(n log n).

Conceptual Overview

Divide: We keep splitting the batch of cupcakes into halves until each sub-batch is a single cupcake (or no cupcakes). A single cupcake doesn’t need sorting!
Conquer: Each of these single-cupcake batches is trivially sorted.
Combine: We start merging the little batches back together. At every merge step, we ensure cupcakes end up in ascending order (least sweet to most sweet).

Time Complexity in a Nutshell

At each level of splitting, we perform O(n) work to merge the halves.
There are about log n levels of splitting (because we divide in half each time).
Multiply them: O(n log n) overall!

Merge Sort Implementation

Let’s dive into the code. We’ll simulate sorting an array of integers. Think of each integer as a cupcake’s “sweetness level.”

public class MyMergeSort {

    /**
     * Recursively splits arr into two halves, sorts each half,
     * and merges them back together.
     */
    public static int[] merge_sort(int[] arr) {
        if (arr.length <= 1) {
            // Base case: already sorted if there's 0 or 1 element
            return arr;
        }

        int mid = arr.length / 2;

        // Split the array into two halves
        int[] left_half = new int[mid];
        int[] right_half = new int[arr.length - mid];

        // Copy the left half
        System.arraycopy(arr, 0, left_half, 0, mid);

        // Copy the right half
        System.arraycopy(arr, mid, right_half, 0, arr.length - mid);

        // Recursively sort each half
        left_half = merge_sort(left_half);
        right_half = merge_sort(right_half);

        // Merge the two sorted halves
        return merge(left_half, right_half);
    }

    /**
     * Merge two sorted arrays (left and right) into a single sorted array.
     */
    public static int[] merge(int[] left, int[] right) {
        int[] merged = new int[left.length + right.length];
        int i = 0, j = 0, k = 0;

        // Compare elements from left and right, picking the smaller one
        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) {
                merged[k++] = left[i++];
            } else {
                merged[k++] = right[j++];
            }
        }

        // If any elements remain in left, add them
        while (i < left.length) {
            merged[k++] = left[i++];
        }

        // If any elements remain in right, add them
        while (j < right.length) {
            merged[k++] = right[j++];
        }

        return merged;
    }
}

Example Usage

Let’s test our Merge Sort by creating a list of sweetness levels. Then we’ll print the sorted result.

import java.util.Arrays;
import java.util.Random;

public class MergeSortUsage {
    public static void main(String[] args) {
        Random random = new Random();

        // Generate random sweetness levels
        int[] cupcake_sweetness = new int[8];
        for (int i = 0; i < cupcake_sweetness.length; i++) {
            cupcake_sweetness[i] = random.nextInt(100) + 1; // random 1-100
        }

        // Print original sweetness levels
        System.out.println("Original sweetness levels: " + Arrays.toString(cupcake_sweetness));

        // Sort using merge_sort
        int[] sorted_sweetness = MyMergeSort.merge_sort(cupcake_sweetness);

        // Print sorted sweetness levels
        System.out.println("Sorted sweetness levels: " + Arrays.toString(sorted_sweetness));
    }
}

Popcorn Hack

Popcorn Hack Challenge: Adapt the merge_sort function so that it sorts in descending order (from most sweet to least sweet) without reversing the array afterward. In other words, handle the comparison logic in the merge step.

Steps to try:

Copy the merge_sort and merge functions.
Adjust the comparison so that the larger element is chosen first.
Test your updated code on a random list of integers to confirm you get a descending result.

Hint: In the while loop of merge(), switch the condition so that we pick the bigger element first.

Example sorting [38, 27, 43, 10]

Divide:

[38, 27, 43, 10] is divided into [38, 27 ] and [43, 10] .
[38, 27] is divided into [38] and [27] .
[43, 10] is divided into [43] and [10] .
Conquer:
[38] is already sorted.
[27] is already sorted.
[43] is already sorted.
[10] is already sorted.
Merge:
Merge [38] and [27] to get [27, 38] .
Merge [43] and [10] to get [10,43] .
Merge [27, 38] and [10,43] to get the final sorted list [10, 27, 38, 43] Therefore, the sorted list is [10, 27, 38, 43] .

Demo

Form a Line
- Eight volunteers stand in a single, unordered line (each wearing a number).
Split Into Halves
- Split into two groups: left half and right half. Then keep splitting until each group is down to a single person.
Merge
- To merge two sorted groups, compare the front individuals’ numbers: the lower number moves first into the new “sorted line.” Continue until all members from both groups stand in sorted order.
Repeat
- Merge sorted pairs into bigger sorted groups. Keep merging until everyone is back in one fully sorted line.

What We Observe

Divide & Conquer: Splitting until single elements are already “sorted.”
Merge Step: Carefully recombines sorted groups by comparing the front members.
Efficiency: Fewer comparisons overall, leading to O(n log n) time.

Watch the line transform from chaos to order—just like code does with real Merge Sort!

Homework Hack

Written Reflection:
- Explain how Merge Sort splits data, merges data, and achieves its O(n log n) efficiency, in your own words.
Inversion Counter (Optional, Extra Challenge):
- Modify the merge process to count how many times elements from the right array are placed before elements of the left array. This count is the number of inversions, a measure of “how unsorted” the list was.
Linked List Sorting (Choose if you’re adventurous):
- Instead of an array or list, implement a Merge Sort for a singly linked list. This can be done by finding the middle node, splitting the list, and then merging.

Show your solutions or answers to these tasks in your own notebook or code environment. Happy sorting!