Guided Project: Sorting II

Master the divide-and-conquer approach through hands-on implementation of Merge Sort.

Understanding Merge Sort

Merge Sort is an efficient, stable sorting algorithm that uses a divide-and-conquer strategy. It divides the input array into smaller subarrays, sorts them recursively, and then merges them back together to produce a sorted array.

Key Concepts

Divide and conquer strategy
Recursive implementation
Time complexity: O(n log n)
Space complexity: O(n)

Learning Objectives

Implement recursive merge sort
Master array merging technique
Understand algorithm complexity

Implementing Merge Sort

Implementation Steps

1
Main Merge Sort Method

Implement the recursive divide step

public void mergeSort(int[] arr, int left, int right) { // Base case: If the subarray has 0 or 1 elements, it's already sorted if (left < right) { // Find the middle point int mid = left + (right - left) / 2; // Sort first and second halves mergeSort(arr, left, mid); mergeSort(arr, mid + 1, right); // Merge the sorted halves merge(arr, left, mid, right); } }

Understanding the Divide Step:
- Base Case: If the subarray has 0 or 1 elements, it's already sorted.
- Recursive Division: The array is split into two halves at the middle point.
- Middle Calculation: mid = left + (right - left) / 2 prevents integer overflow.
- Recursive Calls: Each half is sorted independently using recursive calls.
2
Merge Method

Implement the merge step to combine sorted subarrays

private void merge(int[] arr, int left, int mid, int right) { // Calculate sizes of temporary subarrays int n1 = mid - left + 1; int n2 = right - mid; // Create temporary arrays int[] leftArray = new int[n1]; int[] rightArray = new int[n2]; // Copy data to temporary arrays for (int i = 0; i < n1; i++) { leftArray[i] = arr[left + i]; } for (int j = 0; j < n2; j++) { rightArray[j] = arr[mid + 1 + j]; } // Merge the temporary arrays back into original array int i = 0, j = 0, k = left; while (i < n1 && j < n2) { if (leftArray[i] <= rightArray[j]) { arr[k] = leftArray[i]; i++; } else { arr[k] = rightArray[j]; j++; } k++; } // Copy remaining elements if any while (i < n1) { arr[k] = leftArray[i]; i++; k++; } while (j < n2) { arr[k] = rightArray[j]; j++; k++; } }

Understanding the Merge Process:
1. Create Temporary Arrays: Copy elements from the original array into two temporary subarrays.
2. Compare and Merge: Compare elements from both subarrays and place the smaller element into the original array.
3. Handle Remaining Elements: Copy any remaining elements from either subarray.
3
Algorithm Analysis

Time Complexity
- Worst Case: O(n log n) - Consistent performance regardless of input
- Average Case: O(n log n)
- Best Case: O(n log n) - Even for sorted arrays
Explanation: The divide step takes O(log n) recursive levels, and at each level, the merge operation takes O(n) time, resulting in O(n log n) overall.

Space Complexity
- O(n) - Requires temporary arrays for the merge step
Advantages of Merge Sort:
- Stable: Preserves the relative order of equal elements
- Predictable Performance: O(n log n) in all cases
- External Sorting: Efficiently handles large datasets that don't fit in memory
When to Use Merge Sort:
- When stability is required (preserving order of equal elements)
- When predictable performance is needed regardless of input data
- For external sorting of large datasets
- When linked lists are being sorted (since merge operation is efficient on linked lists)

Visual Example of Merge Sort

Let's visualize how merge sort works with the array [38, 27, 43, 3, 9, 82, 10]:

Divide Phase:

[38, 27, 43, 3, 9, 82, 10]
                  /                  \
       [38, 27, 43, 3]            [9, 82, 10]
         /        \                /       \
    [38, 27]    [43, 3]         [9]     [82, 10]
      /   \       /   \           |       /    \
   [38]  [27]   [43]  [3]        [9]    [82]  [10]

Conquer Phase (Merge back up):

   [38]  [27]   [43]  [3]        [9]    [82]  [10]
      \   /       \   /           |       \    /
    [27, 38]    [3, 43]         [9]     [10, 82]
         \        /                \       /
       [3, 27, 38, 43]            [9, 10, 82]
                  \                  /
               [3, 9, 10, 27, 38, 43, 82]

Step-by-Step Merge Example:

Let's zoom in on the merge step for [27, 38] and [3, 43] → [3, 27, 38, 43]:

Left Array	Right Array	Comparison	Result So Far
[27, 38]	[3, 43]	27 > 3	[3]
[27, 38]	[43]	27 < 43	[3, 27]
[38]	[43]	38 < 43	[3, 27, 38]
[]	[43]	Copy remaining	[3, 27, 38, 43]

Merge Sort Variations

1. In-Place Merge Sort

A version that reduces space complexity by merging subarrays in-place:

private void mergeInPlace(int[] arr, int start, int mid, int end) {
    // Calculate where second array starts
    int start2 = mid + 1;
    
    // If the direct merge is already sorted
    if (arr[mid] <= arr[start2]) {
        return;
    }
    
    // Two pointers to maintain the current position of elements
    while (start <= mid && start2 <= end) {
        // If element 1 is in right place
        if (arr[start] <= arr[start2]) {
            start++;
        } else {
            int value = arr[start2];
            int index = start2;
            
            // Shift all elements between start and start2 right by 1
            while (index != start) {
                arr[index] = arr[index - 1];
                index--;
            }
            arr[start] = value;
            
            // Update pointers
            start++;
            mid++;
            start2++;
        }
    }
}

2. Bottom-Up Merge Sort (Iterative)

A non-recursive implementation that uses iteration:

public void bottomUpMergeSort(int[] arr) {
    int n = arr.length;
    
    // Start with subarrays of size 1, then 2, 4, 8...
    for (int size = 1; size < n; size = 2 * size) {
        // Merge subarrays of size 'size'
        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, leftStart, mid, rightEnd);
        }
    }
}

3. Natural Merge Sort

Takes advantage of pre-existing ordered runs in the input array:

public void naturalMergeSort(int[] arr) {
    int n = arr.length;
    if (n <= 1) return;
    
    boolean sorted = false;
    while (!sorted) {
        sorted = true;
        // Find and merge naturally ordered runs
        int i = 0;
        while (i < n - 1) {
            int j = i;
            // Find end of the first run
            while (j < n - 1 && arr[j] <= arr[j + 1]) j++;
            
            // If not at the end, merge with next run
            if (j < n - 1) {
                int k = j + 1;
                // Find end of the second run
                while (k < n - 1 && arr[k] <= arr[k + 1]) k++;
                
                merge(arr, i, j, k);
                i = k + 1;
                sorted = false;
            } else {
                i = j + 1;
            }
        }
    }
}

Practice Exercises

Exercise 1: Basic Merge Sort

Implement the merge sort algorithm to sort an array in ascending order.

public void mergeSort(int[] arr) {
    // Your implementation here
    // Call mergeSort(arr, 0, arr.length - 1)
}

Test Cases:

[38, 27, 43, 3, 9, 82, 10] → [3, 9, 10, 27, 38, 43, 82]
[5, 2, 8, 1, 9] → [1, 2, 5, 8, 9]
[1, 2, 3, 4, 5] (already sorted) → [1, 2, 3, 4, 5]

Exercise 2: Merge Operation

Implement the merge operation that combines two sorted arrays into a single sorted array.

public int[] merge(int[] arr1, int[] arr2) {
    // Your implementation here
    // Merge two sorted arrays
}

Test Cases:

[1, 3, 5, 7], [2, 4, 6, 8] → [1, 2, 3, 4, 5, 6, 7, 8]
[1, 4, 7], [2, 3, 5] → [1, 2, 3, 4, 5, 7]
[], [1, 2, 3] → [1, 2, 3]

Exercise 3: Descending Merge Sort

Modify the merge sort algorithm to sort in descending order.

public void mergeSortDescending(int[] arr) {
    // Your implementation here
    // Sort array in descending order
}

Test Cases:

[38, 27, 43, 3, 9, 82, 10] → [82, 43, 38, 27, 10, 9, 3]
[5, 2, 8, 1, 9] → [9, 8, 5, 2, 1]

Hint: Only modify the merge operation to place larger elements first.

Exercise 4: Count Inversions

Modify the merge sort algorithm to count the number of inversions in an array (pairs of elements that are out of order).

public long countInversions(int[] arr) {
    // Your implementation here
    // Return the number of inversions in the array
}

Test Cases:

[1, 3, 5, 2, 4, 6] → 3 inversions
[2, 4, 1, 3, 5] → 3 inversions
[5, 4, 3, 2, 1] → 10 inversions

Hint: Count inversions during the merge step.

Exercise 5: Iterative Merge Sort

Implement a bottom-up (iterative) version of merge sort without using recursion.

public void iterativeMergeSort(int[] arr) {
    // Your implementation here
    // Implement merge sort without recursion
}

Test Cases:

[38, 27, 43, 3, 9, 82, 10] → [3, 9, 10, 27, 38, 43, 82]
[5, 2, 8, 1, 9] → [1, 2, 5, 8, 9]

Hint: Use a loop to merge subarrays of increasing size (1, 2, 4, 8...).

Sorting II: Merge Sort Implementation

Understanding Merge Sort

Key Concepts

Learning Objectives

Implementing Merge Sort

Implementation Steps

Main Merge Sort Method

Understanding the Divide Step:

Merge Method

Understanding the Merge Process:

Algorithm Analysis

Time Complexity

Space Complexity

Advantages of Merge Sort:

When to Use Merge Sort:

Visual Example of Merge Sort

Divide Phase:

Conquer Phase (Merge back up):

Step-by-Step Merge Example:

Merge Sort Variations

1. In-Place Merge Sort

2. Bottom-Up Merge Sort (Iterative)

3. Natural Merge Sort

Practice Exercises

Exercise 1: Basic Merge Sort

Test Cases:

Exercise 2: Merge Operation

Test Cases:

Exercise 3: Descending Merge Sort

Test Cases:

Exercise 4: Count Inversions

Test Cases:

Exercise 5: Iterative Merge Sort

Test Cases: