Interactive Divide and Conquer Visualization
Merge Sort
Watch how merge sort divides an array into smaller subarrays, sorts them, and then merges them back together.
Interactive Visualization:
Merge Sort: A divide-and-conquer algorithm that divides the input array into two halves, recursively sorts them, and then merges the sorted halves.
Time Complexity
- Best Case: O(n log n)
- Average Case: O(n log n)
- Worst Case: O(n log n)
Space Complexity
- Auxiliary Space: O(n)
- Requires additional space for the temporary arrays during merging
Step 0 of 84: Initial state
Quick Sort
See how quick sort partitions an array around a pivot element and recursively sorts the resulting subarrays.
Interactive Visualization:
Quick Sort: A divide-and-conquer algorithm that picks an element as a pivot and partitions the array around the pivot, placing smaller elements before it and larger elements after it.
Time Complexity
- Best Case: O(n log n)
- Average Case: O(n log n)
- Worst Case: O(n²) - when the array is already sorted and using first/last element as pivot
Space Complexity
- Auxiliary Space: O(log n) - for the recursion stack
- In-place sorting algorithm (doesn't require additional arrays)
Pivot Selection Strategies
- First Element: Simple but can lead to O(n²) time for sorted arrays
- Last Element: Simple but also can lead to O(n²) time for sorted arrays
- Middle Element: Better performance for sorted or nearly sorted arrays
- Random Element: Good average performance, avoids worst-case scenarios
- Median of Three: Chooses the median of first, middle, and last elements, reducing the chance of picking a bad pivot
Step 0 of 51: Initial state
Closest Pair of Points
Explore how the closest pair of points algorithm divides the plane into two halves and finds the closest pair efficiently.
Interactive Visualization:
Closest Pair of Points: A divide-and-conquer algorithm that finds the pair of points with the smallest distance between them in a set of points in a plane.
Time Complexity
- Brute Force: O(n²)
- Divide and Conquer: O(n log n)
- Sorting points takes O(n log n)
- Recursive calls take T(n) = 2T(n/2) + O(n)
Algorithm Steps
- Sort points by x-coordinate
- Divide the points into two halves
- Recursively find the closest pair in each half
- Find the minimum distance d from the two halves
- Create a strip of points within d distance of the dividing line
- Find the closest pair in the strip (if any)
- Return the overall closest pair
Key Insight
The key insight of this algorithm is that we only need to check a limited number of points in the strip. It can be proven mathematically that for each point in the strip, we only need to check at most 7 points ahead of it (in y-coordinate order). This is because if we have more points within a d×d square, at least two of them must be closer than distance d.
Step 0 of 54: Initial state
Learning Objective
Visualize how divide and conquer algorithms work through interactive examples of classic problems.
Visualizing Divide and Conquer
Divide and conquer algorithms can be challenging to understand without seeing them in action. These visualizations will help you grasp how these algorithms break down problems and build solutions.
Merge Sort
Watch how merge sort divides an array into smaller subarrays, sorts them, and then merges them back together.
Quick Sort
See how quick sort partitions an array around a pivot element and recursively sorts the resulting subarrays.
Closest Pair of Points
Explore how the closest pair of points algorithm divides the plane into two halves and finds the closest pair efficiently.
Merge Sort
Watch how merge sort divides an array into smaller subarrays, sorts them, and then merges them back together.
Interactive Visualization:
Merge Sort: A divide-and-conquer algorithm that divides the input array into two halves, recursively sorts them, and then merges the sorted halves.
Time Complexity
- Best Case: O(n log n)
- Average Case: O(n log n)
- Worst Case: O(n log n)
Space Complexity
- Auxiliary Space: O(n)
- Requires additional space for the temporary arrays during merging
Step 0 of 110: Initial state
How it works: Merge sort divides the array in half, recursively sorts each half, and then merges the sorted halves. The merge step compares elements from both halves and combines them in sorted order.
Merge Sort Properties
Merge Sort is a classic divide-and-conquer algorithm with several important properties:
- Stable Sort: Merge Sort preserves the relative order of equal elements.
- Not In-Place: Requires additional memory proportional to the size of the input array.
- Predictable Performance: Always O(n log n) time complexity regardless of the input.
- External Sort: Well-suited for sorting large datasets that don't fit in memory.
- Parallelizable: The divide step can be parallelized, making it efficient for multi-core systems.
The visualization shows how Merge Sort recursively divides the array until it reaches subarrays of size 1, then merges them back together in sorted order.
Notice how the algorithm always divides the array in half, regardless of the input data, which is why it maintains its O(n log n) performance even in worst-case scenarios.