Back to Welcome 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

function quickSort(arr, left = 0, right = arr.length - 1) {
    if (left < right) {
        const pivotIndex = partition(arr, left, right);
        quickSort(arr, left, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, right);
    }
    return arr;
}

function partition(arr, left, right) {
    const pivot = arr[right];
    let i = left - 1;

    for (let j = left; j < right; j++) {
        if (arr[j] <= pivot) {
            i++;
            [arr[i], arr[j]] = [arr[j], arr[i]];
        }
    }

    [arr[i + 1], arr[right]] = [arr[right], arr[i + 1]];
    return i + 1;
}

Merge Sort Implementation

function mergeSort(arr) {
    if (arr.length <= 1) return arr;

    const mid = Math.floor(arr.length / 2);
    const left = mergeSort(arr.slice(0, mid));
    const right = mergeSort(arr.slice(mid));

    return merge(left, right);
}

function merge(left, right) {
    const result = [];
    let i = 0, j = 0;

    while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) {
            result.push(left[i++]);
        } else {
            result.push(right[j++]);
        }
    }

    return result.concat(left.slice(i)).concat(right.slice(j));
}

Usage Example:

const arr1 = [64, 34, 25, 12, 22, 11, 90];
console.log('Quicksort:', quickSort([...arr1]));
console.log('Merge sort:', mergeSort([...arr1]));

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