Back to Main ACS Page

Module 2: Advanced Sorting Algorithms

Master the divide-and-conquer approach with Quicksort and Merge Sort. Learn how these efficient algorithms tackle complex sorting problems.

Learning Objectives

Core Concepts

Understand divide and conquer strategy
Implement Quicksort algorithm
Implement Merge Sort algorithm
Analyze time and space complexity

Key Skills

Algorithm analysis
Recursive problem solving
Performance optimization
Space-time trade-offs

Algorithm Comparison

Quicksort

Average case: O(n log n)
In-place sorting
Efficient for random data
Widely used in practice

Merge Sort

Guaranteed O(n log n)
Stable sorting algorithm
Requires extra space
Good for linked lists

Quicksort

Key Concepts

Algorithm Steps

Choose a pivot element
Partition around pivot
Recursively sort subarrays
Combine results

Optimization Tips

Choose median as pivot
Handle small subarrays differently
Use insertion sort for small n
Implement tail recursion

Merge Sort

Understanding Merge Sort

Algorithm Steps

Divide array into halves
Recursively sort halves
Merge sorted halves
Copy back to original array

Key Features

Stable sorting algorithm
Predictable performance
Parallel-friendly
External sorting capable

Implementation Examples

Quicksort Implementation

public static void quickSort(int[] arr, int left, int right) {
    if (left < right) {
        int pivotIndex = partition(arr, left, right);
        quickSort(arr, left, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, right);
    }
}

private static int partition(int[] arr, int left, int right) {
    int pivot = arr[right];
    int i = left - 1;
    for (int j = left; j < right; j++) {
        if (arr[j] <= pivot) {
            i++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    int temp = arr[i + 1];
    arr[i + 1] = arr[right];
    arr[right] = temp;
    return i + 1;
}

Merge Sort Implementation

public static int[] mergeSort(int[] arr) {
    if (arr.length <= 1) return arr;
    int mid = arr.length / 2;
    int[] left = Arrays.copyOfRange(arr, 0, mid);
    int[] right = Arrays.copyOfRange(arr, mid, arr.length);
    return merge(mergeSort(left), mergeSort(right));
}

private static int[] merge(int[] left, int[] right) {
    int[] result = new int[left.length + right.length];
    int i = 0, j = 0, k = 0;
    while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) {
            result[k++] = left[i++];
        } else {
            result[k++] = right[j++];
        }
    }
    while (i < left.length) {
        result[k++] = left[i++];
    }
    while (j < right.length) {
        result[k++] = right[j++];
    }
    return result;
}

Usage Example:

int[] arr1 = {64, 34, 25, 12, 22, 11, 90};
quickSort(arr1, 0, arr1.length - 1);
System.out.println("Quicksort: " + Arrays.toString(arr1));
int[] arr2 = {64, 34, 25, 12, 22, 11, 90};
System.out.println("Merge sort: " + Arrays.toString(mergeSort(arr2)));

Practice Exercises

Exercise 1: Hybrid Sort

Implement a hybrid sorting algorithm that uses both Quicksort and Insertion Sort.

Requirements:

Use Quicksort for large subarrays (n > 10)
Use Insertion Sort for small subarrays
Maintain O(n log n) average case
Improve practical performance

Exercise 2: K-way Merge

Extend the merge sort algorithm to handle k sorted arrays simultaneously.

Example:

const arrays = [
    [1, 4, 7],
    [2, 5, 8],
    [3, 6, 9]
];

console.log(kWayMerge(arrays));
// Output: [1, 2, 3, 4, 5, 6, 7, 8, 9]

Exercise 3: Custom Comparator

Modify both sorting algorithms to work with custom comparison functions.

Example Usage:

const people = [
    { name: 'Alice', age: 30 },
    { name: 'Bob', age: 25 },
    { name: 'Charlie', age: 35 }
];

// Sort by age
quickSort(people, (a, b) => a.age - b.age);

// Sort by name
mergeSort(people, (a, b) => a.name.localeCompare(b.name));

Module 2: Advanced Sorting Algorithms

Learning Objectives

Core Concepts

Key Skills

Algorithm Comparison

Quicksort

Merge Sort

Quicksort

Key Concepts

Algorithm Steps

Optimization Tips

Merge Sort

Understanding Merge Sort

Algorithm Steps

Key Features

Implementation Examples

Quicksort Implementation

Merge Sort Implementation

Usage Example:

Practice Exercises

Exercise 1: Hybrid Sort

Requirements:

Exercise 2: K-way Merge

Example:

Exercise 3: Custom Comparator

Example Usage:

LeetCode Sorting Problem Collection

Beginner Sorting Problems

Intermediate Sorting Problems