Algorithms and Problem Solving with Java
Merge Sort and Quick Sort
You are viewing a free preview lesson.
Lesson Overview
আগের lesson-এ আমরা তিনটি simple sorting algorithm শিখেছি:
Bubble Sort
Selection Sort
Insertion Sort
এগুলোর worst-case time complexity ছিল:
O(n²)
Small input-এর জন্য এটি acceptable হতে পারে।
কিন্তু input বড় হলে quadratic growth দ্রুত expensive হয়ে যায়।
Example:
n = 1,000
n²
≈ 1,000,000
while:
n log₂ n
≈ 10,000
এই difference input আরও বড় হলে dramatically বাড়ে।
এই কারণে general-purpose sorting-এর জন্য আমাদের আরও scalable algorithms দরকার।
এই lesson-এ আমরা দুইটি fundamental efficient sorting strategy শিখব:
Merge Sort
Quick Sort
দুইটিই divide-and-conquer idea ব্যবহার করে, কিন্তু তাদের approach different।
এই lesson-এ আমরা শিখব:
- What divide and conquer means
- Why
O(n²)sorting becomes expensive - Merge Sort
- Splitting arrays
- Recursive sorting
- Merging sorted ranges
- Merge Sort complexity
- Merge Sort memory cost
- Quick Sort
- Pivot selection
- Partitioning
- Recursive subranges
- Quick Sort average and worst case
- In-place sorting
- Merge Sort vs Quick Sort
- Stability
- Why production implementations are more sophisticated
Why Do We Need Better Sorting Algorithms?
Suppose we have:
100 values
An O(n²) algorithm may perform on the order of:
10,000
operations।
Not terrible।
But with:
100,000 values
quadratic work is on the order of:
10,000,000,000
That is:
10 billion
A much more scalable growth rate is:
O(n log n)
For the same:
100,000 values
roughly:
100,000 × 17
≈ 1,700,000
The exact operation counts vary, but the growth difference is enormous।
Divide and Conquer
Both Merge Sort and Quick Sort belong to a broad algorithmic strategy called:
Divide and Conquer
The general idea is:
1. Divide a large problem into smaller problems.
2. Solve the smaller problems.
3. Combine or organize their results.
Recursion often expresses this naturally।
A Simple Analogy
Suppose you have:
1,000 exam papers
Instead of one person trying to sort everything at once, you could:
Split into smaller groups
Sort each group
Combine the sorted groups
This resembles Merge Sort।
Quick Sort instead organizes values around a chosen reference value, called a:
pivot
and recursively sorts the resulting regions।
Merge Sort
Merge Sort follows this high-level strategy:
Split
Sort smaller halves
Merge sorted halves
Example:
[8, 3, 5, 1]
Split:
[8, 3] [5, 1]
Split again:
[8] [3] [5] [1]
Single-element arrays are already sorted।
Then merge:
[8] + [3]
→ [3, 8]
[5] + [1]
→ [1, 5]
Then final merge:
[3, 8] + [1, 5]
→ [1, 3, 5, 8]
Merge Sort Base Case
A single-element range is already sorted।
So recursion can stop when:
size <= 1
That is our base case।
Divide Step
Suppose current range is:
left ... right
We calculate:
int middle =
left
+ (
right - left
) / 2;
Then recursively sort:
left ... middle
and:
middle + 1 ... right
Merge Sort Structure
Conceptually:
mergeSort(
values,
left,
right
) {
if range has one or zero values:
return
find middle
mergeSort(left half)
mergeSort(right half)
merge(sorted halves)
}
Merge Sort Implementation
static void mergeSort(
int[] numbers
) {
if (
numbers.length < 2
) {
return;
}
int[] buffer =
new int[
numbers.length
];
mergeSort(
numbers,
buffer,
0,
numbers.length - 1
);
}
static void mergeSort(
int[] numbers,
int[] buffer,
int left,
int right
) {
if (
left >= right
) {
return;
}
int middle =
left
+ (
right - left
) / 2;
mergeSort(
numbers,
buffer,
left,
middle
);
mergeSort(
numbers,
buffer,
middle + 1,
right
);
merge(
numbers,
buffer,
left,
middle,
right
);
}
The sorting logic is not complete yet।
The key operation is:
merge
Merging Two Sorted Ranges
Suppose we already have:
[2, 5, 9]
and:
[1, 4, 8]
Both halves are sorted।
We compare the first available value from each side।
2 vs 1
→ take 1
Then:
2 vs 4
→ take 2
Then:
5 vs 4
→ take 4
Continue until one side is exhausted।
Merge Example
Input halves:
Left:
[2, 5, 9]
Right:
[1, 4, 8]
Result:
[1, 2, 4, 5, 8, 9]
The merge operation is linear because each value is processed once।
Merge Implementation
static void merge(
int[] numbers,
int[] buffer,
int left,
int middle,
int right
) {
int leftIndex =
left;
int rightIndex =
middle + 1;
int bufferIndex =
left;
while (
leftIndex <= middle
&& rightIndex <= right
) {
if (
numbers[leftIndex]
<= numbers[rightIndex]
) {
buffer[bufferIndex] =
numbers[leftIndex];
leftIndex++;
} else {
buffer[bufferIndex] =
numbers[rightIndex];
rightIndex++;
}
bufferIndex++;
}
while (
leftIndex <= middle
) {
buffer[bufferIndex] =
numbers[leftIndex];
leftIndex++;
bufferIndex++;
}
while (
rightIndex <= right
) {
buffer[bufferIndex] =
numbers[rightIndex];
rightIndex++;
bufferIndex++;
}
for (
int i = left;
i <= right;
i++
) {
numbers[i] =
buffer[i];
}
}
Why Three while Loops?
The first loop runs while both halves still have values।
Then one side may finish before the other।
Example:
Left:
[1, 2]
Right:
[3, 4, 5]
After copying 1 and 2, the left side is finished।
Remaining:
3 4 5
must still be copied।
That is why we have separate loops for remaining values।
Complete Merge Sort
static void mergeSort(
int[] numbers
) {
if (
numbers.length < 2
) {
return;
}
int[] buffer =
new int[
numbers.length
];
mergeSort(
numbers,
buffer,
0,
numbers.length - 1
);
}
static void mergeSort(
int[] numbers,
int[] buffer,
int left,
int right
) {
if (
left >= right
) {
return;
}
int middle =
left
+ (
right - left
) / 2;
mergeSort(
numbers,
buffer,
left,
middle
);
mergeSort(
numbers,
buffer,
middle + 1,
right
);
merge(
numbers,
buffer,
left,
middle,
right
);
}
static void merge(
int[] numbers,
int[] buffer,
int left,
int middle,
int right
) {
int leftIndex =
left;
int rightIndex =
middle + 1;
int bufferIndex =
left;
while (
leftIndex <= middle
&& rightIndex <= right
) {
if (
numbers[leftIndex]
<= numbers[rightIndex]
) {
buffer[bufferIndex] =
numbers[leftIndex];
leftIndex++;
} else {
buffer[bufferIndex] =
numbers[rightIndex];
rightIndex++;
}
bufferIndex++;
}
while (
leftIndex <= middle
) {
buffer[bufferIndex] =
numbers[leftIndex];
leftIndex++;
bufferIndex++;
}
while (
rightIndex <= right
) {
buffer[bufferIndex] =
numbers[rightIndex];
rightIndex++;
bufferIndex++;
}
for (
int i = left;
i <= right;
i++
) {
numbers[i] =
buffer[i];
}
}
Trace Merge Sort
Input:
[8, 3, 5, 1]
First call:
left = 0
right = 3
middle = 1
Split:
[8, 3]
[5, 1]
Left Half
[8, 3]
Split:
[8]
[3]
Both single-element ranges are sorted।
Merge:
[3, 8]
Right Half
[5, 1]
Split:
[5]
[1]
Merge:
[1, 5]
Final Merge
Now:
[3, 8]
and:
[1, 5]
Merge:
1
3
5
8
Final:
[1, 3, 5, 8]
Why Merge Sort Is O(n log n)
Think in levels।
For:
8 elements
splitting looks like:
8
↓
4 + 4
↓
2 + 2 + 2 + 2
↓
1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
Number of split levels:
log₂ n
Work Per Level
At each merge level, all n values are processed across the different merges।
So:
O(n) work per level
and:
O(log n) levels
Total:
O(n log n)
Merge Sort Time Complexity
Merge Sort provides:
Best: O(n log n)
Average: O(n log n)
Worst: O(n log n)
This predictability is one of its strengths।
Merge Sort Space Complexity
Our implementation allocates:
int[] buffer =
new int[
numbers.length
];
So additional array storage is:
O(n)
Recursion also uses:
O(log n)
call-stack depth।
The dominant extra space is:
O(n)
Merge Sort Is Not In-Place Here
Our implementation uses an additional buffer of size n।
So it is not an O(1) extra-space in-place algorithm।
This is a major tradeoff:
Excellent predictable time
but additional memory
Merge Sort Stability
Notice the comparison:
if (
numbers[leftIndex]
<= numbers[rightIndex]
)
When values are equal, the left-side value is chosen first।
That preserves relative ordering across equal elements।
Therefore this style of Merge Sort is stable।
Why Stability Matters Again
Suppose objects are sorted by score:
Sakib score=90
Subu score=80
Sumu score=90
If Sakib appears before Sumu originally, a stable sort by score can preserve that order among equal score values।
Quick Sort
Quick Sort uses divide-and-conquer too, but its strategy is different।
It chooses a value called a:
Pivot
Then rearranges the current range so values fall around the pivot。
Conceptually:
smaller values
pivot
larger values
Then recursively sort the left and right regions।
Quick Sort High-Level Flow
Example:
[8, 3, 5, 1, 7]
Suppose pivot is:
7
Partition into something like:
[3, 5, 1] 7 [8]
Then recursively sort:
[3, 5, 1]
and:
[8]
What Is Partitioning?
Partitioning reorganizes a range around a pivot so that after partitioning:
Values on one side satisfy one ordering condition
Pivot reaches an appropriate position
Values on the other side satisfy the opposite condition
The exact arrangement depends on the partition scheme।
A Simple Lomuto-Style Partition
One common textbook implementation chooses:
Last element as pivot
Example:
int pivot =
numbers[right];
Then scan values from left to right。
Partition Implementation
static int partition(
int[] numbers,
int left,
int right
) {
int pivot =
numbers[right];
int smallerEnd =
left - 1;
for (
int i = left;
i < right;
i++
) {
if (
numbers[i]
<= pivot
) {
smallerEnd++;
swap(
numbers,
smallerEnd,
i
);
}
}
int pivotIndex =
smallerEnd + 1;
swap(
numbers,
pivotIndex,
right
);
return pivotIndex;
}
Understanding smallerEnd
smallerEnd tracks the end of the region containing values:
<= pivot
Initially:
left - 1
means:
No smaller/equal values have been placed yet.
Partition Trace
Input:
[8, 3, 5, 1, 7]
Pivot:
7
Start:
smallerEnd = -1
Check 8
8 <= 7?
No
No change।
Check 3
3 <= 7?
Yes
Move boundary:
smallerEnd = 0
Swap current 3 with index 0:
[3, 8, 5, 1, 7]
Check 5
5 <= 7?
Yes
Boundary:
1
Swap:
[3, 5, 8, 1, 7]
Check 1
1 <= 7?
Yes
Boundary:
2
Swap:
[3, 5, 1, 8, 7]
Place Pivot
After scan:
smallerEnd = 2
Pivot destination:
3
Swap 7 with 8:
[3, 5, 1, 7, 8]
Pivot index:
3
Now:
Left of pivot:
3 5 1
Pivot:
7
Right:
8
Quick Sort Implementation
static void quickSort(
int[] numbers
) {
quickSort(
numbers,
0,
numbers.length - 1
);
}
static void quickSort(
int[] numbers,
int left,
int right
) {
if (
left >= right
) {
return;
}
int pivotIndex =
partition(
numbers,
left,
right
);
quickSort(
numbers,
left,
pivotIndex - 1
);
quickSort(
numbers,
pivotIndex + 1,
right
);
}
With:
static int partition(
int[] numbers,
int left,
int right
) {
int pivot =
numbers[right];
int smallerEnd =
left - 1;
for (
int i = left;
i < right;
i++
) {
if (
numbers[i]
<= pivot
) {
smallerEnd++;
swap(
numbers,
smallerEnd,
i
);
}
}
int pivotIndex =
smallerEnd + 1;
swap(
numbers,
pivotIndex,
right
);
return pivotIndex;
}
Complete Quick Sort with Swap
static void quickSort(
int[] numbers
) {
quickSort(
numbers,
0,
numbers.length - 1
);
}
static void quickSort(
int[] numbers,
int left,
int right
) {
if (
left >= right
) {
return;
}
int pivotIndex =
partition(
numbers,
left,
right
);
quickSort(
numbers,
left,
pivotIndex - 1
);
quickSort(
numbers,
pivotIndex + 1,
right
);
}
static int partition(
int[] numbers,
int left,
int right
) {
int pivot =
numbers[right];
int smallerEnd =
left - 1;
for (
int i = left;
i < right;
i++
) {
if (
numbers[i]
<= pivot
) {
smallerEnd++;
swap(
numbers,
smallerEnd,
i
);
}
}
int pivotIndex =
smallerEnd + 1;
swap(
numbers,
pivotIndex,
right
);
return pivotIndex;
}
static void swap(
int[] numbers,
int firstIndex,
int secondIndex
) {
int temporary =
numbers[firstIndex];
numbers[firstIndex] =
numbers[secondIndex];
numbers[secondIndex] =
temporary;
}
Quick Sort Base Case
Same general recursive idea:
if (
left >= right
) {
return;
}
A range with zero or one element is already sorted।
Quick Sort Average Complexity
When pivots divide data reasonably well:
roughly balanced partitions
recursion depth is around:
O(log n)
and total work per level is around:
O(n)
So average behavior is:
O(n log n)
Quick Sort Worst Case
Quick Sort can degrade to:
O(n²)
if partitioning repeatedly produces extremely unbalanced ranges।
Example with our last-element pivot strategy:
[1, 2, 3, 4, 5]
Pivot:
5
Partition:
[1, 2, 3, 4] 5
Next pivot:
4
Then:
[1, 2, 3] 4
This keeps shrinking by only one value।
Worst-Case Recursion Shape
Balanced:
n
↓
n/2 n/2
↓
...
Depth:
O(log n)
Bad partitioning:
n
↓
n - 1
↓
n - 2
↓
n - 3
...
Depth:
O(n)
Total time:
O(n²)
Pivot Choice Matters
Our textbook implementation chooses:
Last element
because it is easy to understand।
Production-quality Quick Sort variants may use better strategies such as:
Randomized pivot
Median-based heuristics
Multiple pivots
Hybrid algorithms
to reduce pathological behavior।
Quick Sort Space Complexity
Quick Sort does not require an additional full n-sized array in this implementation।
Partitioning happens inside the original array।
So array storage beyond the input is roughly:
O(1)
But recursion consumes stack space।
Average balanced recursion:
O(log n)
Worst case:
O(n)
Is Quick Sort In-Place?
This implementation is generally described as in-place because partitioning rearranges the original array and does not allocate another full-size array।
However, recursion still uses stack memory।
So "in-place" does not mean:
literally zero extra memory
It normally means:
No additional storage proportional to the full input is required for the elements.
Quick Sort Stability
Typical in-place Quick Sort implementations are:
Not stable
Partition swaps can change the relative order of equal elements।
Merge Sort vs Quick Sort
A high-level comparison:
| Property | Merge Sort | Quick Sort |
|---|---|---|
| Average time | O(n log n) | O(n log n) |
| Worst time | O(n log n) | O(n²) textbook version |
| Extra array space | O(n) | No full-size extra array |
| Recursion | Yes | Yes |
| Stable | Can be stable | Usually not |
| Main operation | Merge sorted halves | Partition around pivot |
Why Use Quick Sort If Worst Case Is Worse?
Because with good pivot strategies, Quick Sort often performs extremely well in practice on arrays।
It benefits from:
Good locality
Low extra memory
Efficient partitioning
But production implementations need to guard against pathological cases।
Why Use Merge Sort?
Merge Sort provides predictable:
O(n log n)
worst-case behavior and can be stable।
It also works naturally with structures or workflows where merging sequential data is efficient।
The cost is:
Additional memory
for common array implementations।
Merge Sort on Linked Structures
Conceptually, Merge Sort can work particularly naturally with linked data structures because merging can be done by relinking nodes rather than repeatedly moving array elements।
We are not implementing linked-list Merge Sort here, but this illustrates that:
Algorithm choice depends on data structure.
Divide-and-Conquer Difference
Merge Sort:
Divide first
Then combine sorted results
Quick Sort:
Partition first
Then recursively sort resulting regions
This is a very useful distinction।
Merge Sort Mental Model
Break down
↓
Single-element pieces
↓
Build back up in sorted order
Quick Sort Mental Model
Choose pivot
↓
Arrange values around pivot
↓
Recursively organize left and right
Recursion Tree Intuition
Merge Sort generally creates balanced recursive halves:
n
/ \
n/2 n/2
/ \
...
Quick Sort depends on pivot quality:
Good:
n
/ \
~n/2 ~n/2
Bad:
n
\
n-1
\
n-2
Example: Merge Sort on Already Sorted Data
Input:
1 2 3 4 5 6
Standard Merge Sort still splits and merges।
Time remains:
O(n log n)
It does not automatically become O(n) simply because the data is already sorted।
Optimizations are possible, but the standard model remains O(n log n)।
Example: Quick Sort on Already Sorted Data
With naive last-element pivot:
1 2 3 4 5 6
every pivot is the largest remaining element।
This creates highly unbalanced partitions।
Worst-case behavior:
O(n²)
This is why pivot strategy matters։
Handling Duplicates
Both algorithms can sort duplicates।
Example:
5 3 5 1 3
Result:
1 3 3 5 5
But duplicate-heavy input can affect Quick Sort partition behavior depending on the partition scheme।
Production implementations often include strategies specifically designed to handle duplicates efficiently।
Three-Way Partitioning Preview
A more advanced Quick Sort variation can partition into:
< pivot
= pivot
> pivot
This can work especially well when many duplicate values exist।
We do not need to implement it in this foundation lesson।
The important point is:
Textbook Quick Sort is not the final word on Quick Sort.
Sorting Objects
Both Merge Sort and Quick Sort fundamentally need an ordering rule।
For integers:
a <= b
For objects, we'd use something like:
Comparator<Course>
Then instead of:
numbers[leftIndex]
<= numbers[rightIndex]
we might conceptually ask:
comparator.compare(
first,
second
) <= 0
We'll focus on Java's standard sorting APIs and comparators in the next lesson।
Integer Overflow in Comparison
Avoid custom comparisons like:
return first - second;
for arbitrary int values because subtraction can overflow।
Prefer:
Integer.compare(
first,
second
);
This becomes especially relevant when implementing comparators।
Production Java Does More Than Textbook Algorithms
Real Java sorting implementations do not simply copy these textbook methods line for line।
Production libraries use techniques such as:
Specialized primitive sorting
Hybrid algorithms
Run detection
Small-range optimizations
Pivot heuristics
Different algorithms for different data types
The exact implementation can change across Java versions।
The lesson is:
Understand the algorithmic foundations
but rely on the standard library for ordinary sorting.
Why Standard Libraries Use Hybrid Strategies
No single sorting technique is best for every input shape।
Example:
Insertion Sort
can be excellent for very small ranges।
A larger algorithm may therefore recursively divide data and eventually switch to insertion-style logic for small partitions।
This is called a:
Hybrid algorithm
Algorithm Engineering vs Textbook Algorithms
Textbook goal:
Teach the core strategy clearly.
Production goal:
Handle real input efficiently,
safely,
predictably,
and with low overhead.
Both matter, but they have different priorities।
Merge Sort and Binary Search Are Different
Both involve dividing ranges, but do not confuse them।
Binary Search:
Search one sorted range
Discard half
O(log n)
Merge Sort:
Sort both halves
Merge everything
O(n log n)
Quick Sort and Binary Search Are Also Different
Quick Sort uses a pivot to partition:
before recursive sorting
Binary Search uses an already sorted collection to eliminate irrelevant halves:
during lookup
Common Mistake 1 — Forgetting the Merge Step
This is not enough:
mergeSort(
left half
);
mergeSort(
right half
);
The halves may individually be sorted but still need to be combined into one sorted range।
Common Mistake 2 — Wrong Merge Boundary
The left half is:
left ... middle
The right half is:
middle + 1 ... right
Be consistent with inclusive boundaries।
Common Mistake 3 — Forgetting Remaining Merge Values
After the main comparison loop ends, one side may still contain values।
Those must be copied।
Common Mistake 4 — Allocating Arrays in Every Merge Unnecessarily
A simple implementation might create many temporary arrays recursively।
For learning, that can be easier to understand।
But our version creates one reusable:
buffer
for the whole sorting process।
This reduces repeated allocation।
Common Mistake 5 — Thinking Merge Sort Is O(log n)
Splitting depth is:
O(log n)
but every level processes all:
n
elements through merging।
Therefore total is:
O(n log n)
Common Mistake 6 — Thinking Quick Sort Is Always O(n log n)
Average behavior may be:
O(n log n)
but textbook Quick Sort can degrade to:
O(n²)
with poor partitions।
Common Mistake 7 — Including Pivot in Recursive Range
After partition:
pivot is already in its partition position.
Recursive ranges should exclude it:
left,
pivotIndex - 1
and:
pivotIndex + 1,
right
Common Mistake 8 — Recursive Range Does Not Shrink
If recursive boundaries include the same unchanged range repeatedly, recursion will not terminate।
Always verify:
Does each recursive call operate on a smaller range?
Common Mistake 9 — Calling Quick Sort Stable
The common in-place partition implementation is not stable।
Do not assume all sorting algorithms preserve equal-element ordering।
Common Mistake 10 — Reimplementing These in Normal Application Code
Use manual implementations for:
Learning
Special algorithmic requirements
Research
Very specific performance work
For ordinary sorting:
Arrays.sort(...)
or:
List.sort(...)
is usually the correct choice।
Practical Example — Compare the Results
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int[] original = {
8,
3,
5,
1,
9,
2
};
int[] mergeValues =
Arrays.copyOf(
original,
original.length
);
int[] quickValues =
Arrays.copyOf(
original,
original.length
);
mergeSort(
mergeValues
);
quickSort(
quickValues
);
System.out.println(
Arrays.toString(
mergeValues
)
);
System.out.println(
Arrays.toString(
quickValues
)
);
}
static void mergeSort(
int[] numbers
) {
if (
numbers.length < 2
) {
return;
}
int[] buffer =
new int[
numbers.length
];
mergeSort(
numbers,
buffer,
0,
numbers.length - 1
);
}
static void mergeSort(
int[] numbers,
int[] buffer,
int left,
int right
) {
if (
left >= right
) {
return;
}
int middle =
left
+ (
right - left
) / 2;
mergeSort(
numbers,
buffer,
left,
middle
);
mergeSort(
numbers,
buffer,
middle + 1,
right
);
merge(
numbers,
buffer,
left,
middle,
right
);
}
static void merge(
int[] numbers,
int[] buffer,
int left,
int middle,
int right
) {
int leftIndex =
left;
int rightIndex =
middle + 1;
int bufferIndex =
left;
while (
leftIndex <= middle
&& rightIndex <= right
) {
if (
numbers[leftIndex]
<= numbers[rightIndex]
) {
buffer[bufferIndex] =
numbers[leftIndex];
leftIndex++;
} else {
buffer[bufferIndex] =
numbers[rightIndex];
rightIndex++;
}
bufferIndex++;
}
while (
leftIndex <= middle
) {
buffer[bufferIndex] =
numbers[leftIndex];
leftIndex++;
bufferIndex++;
}
while (
rightIndex <= right
) {
buffer[bufferIndex] =
numbers[rightIndex];
rightIndex++;
bufferIndex++;
}
for (
int i = left;
i <= right;
i++
) {
numbers[i] =
buffer[i];
}
}
static void quickSort(
int[] numbers
) {
quickSort(
numbers,
0,
numbers.length - 1
);
}
static void quickSort(
int[] numbers,
int left,
int right
) {
if (
left >= right
) {
return;
}
int pivotIndex =
partition(
numbers,
left,
right
);
quickSort(
numbers,
left,
pivotIndex - 1
);
quickSort(
numbers,
pivotIndex + 1,
right
);
}
static int partition(
int[] numbers,
int left,
int right
) {
int pivot =
numbers[right];
int smallerEnd =
left - 1;
for (
int i = left;
i < right;
i++
) {
if (
numbers[i]
<= pivot
) {
smallerEnd++;
swap(
numbers,
smallerEnd,
i
);
}
}
int pivotIndex =
smallerEnd + 1;
swap(
numbers,
pivotIndex,
right
);
return pivotIndex;
}
static void swap(
int[] numbers,
int firstIndex,
int secondIndex
) {
int temporary =
numbers[firstIndex];
numbers[firstIndex] =
numbers[secondIndex];
numbers[secondIndex] =
temporary;
}
}
Output:
[1, 2, 3, 5, 8, 9]
[1, 2, 3, 5, 8, 9]
Practice 1 — Divide and Conquer
What are the three broad stages of divide and conquer?
Answer
Divide
Solve smaller problems
Combine or organize results
Practice 2 — Merge Sort Split
Given:
[8, 4, 6, 2]
show the split structure।
Answer
[8, 4, 6, 2]
→ [8, 4] [6, 2]
→ [8] [4] [6] [2]
Practice 3 — Merge Two Sorted Arrays Conceptually
Merge:
[2, 7, 9]
and:
[1, 5, 8]
Answer
[1, 2, 5, 7, 8, 9]
Practice 4 — Merge Sort Complexity
What is Merge Sort worst-case time?
Answer
O(n log n)
Practice 5 — Merge Sort Space
What is the dominant additional space for the implementation shown?
Answer
O(n)
because of the reusable buffer।
Practice 6 — Merge Sort Stability
Can the implementation shown be stable?
Answer
Yes।
When equal values are encountered, it takes the left value first because the condition uses:
<=
Practice 7 — Quick Sort Pivot
In this implementation, which value is selected as pivot?
Answer
The last value in the current range.
Practice 8 — Partition
Given:
[6, 2, 8, 3, 5]
with pivot:
5
after partition, what must be true?
Answer
The pivot reaches a partition position where values classified to the left are <= 5 and values remaining on the right are > 5 according to the shown partition scheme।
The exact internal order of those regions does not have to be sorted yet।
Practice 9 — Is Partitioning Sorting?
After one Quick Sort partition, are both sides fully sorted?
Answer
No।
Partitioning only organizes the current range around the pivot।
The left and right regions still require recursive sorting।
Practice 10 — Quick Sort Complexity
Typical average:
?
Worst:
?
Answer
Average:
O(n log n)
Worst:
O(n²)
for the textbook implementation।
Practice 11 — Worst-Case Pivot
Why can last-element pivot perform badly on already sorted input?
Answer
Because each pivot may become the largest remaining value, producing highly unbalanced partitions of sizes roughly:
n - 1
and
0
repeatedly।
Practice 12 — Choose the Tradeoff
Which has predictable O(n log n) worst-case time in this lesson?
Answer
Merge Sort
Practice 13 — Extra Array Memory
Which requires a full O(n) buffer in the implementation shown?
Answer
Merge Sort
Practice 14 — Stability
Which common implementation is typically unstable?
Answer
Quick Sort
Practice 15 — Production Sorting
Should you normally replace:
Arrays.sort(
values
);
with your own textbook Quick Sort?
Answer
No।
Use Java's standard implementation unless there is a specific reason to implement custom sorting।
True or False
- Merge Sort uses divide and conquer.
- Merge Sort requires merging sorted subranges.
- Merge Sort worst-case time is
O(n²). - Merge Sort commonly uses
O(n)extra array space. - Merge Sort can be stable.
- Quick Sort uses a pivot.
- Partitioning always fully sorts both sides.
- Quick Sort average performance can be
O(n log n). - Textbook Quick Sort can degrade to
O(n²). - Pivot choice can affect Quick Sort performance.
- The Quick Sort implementation shown allocates a second full-size array.
- Typical in-place Quick Sort is stable.
- Merge Sort and Quick Sort use identical divide-and-conquer mechanics.
- Standard library sorting should normally be preferred in application code.
Answers
1. True
2. True
3. False
4. True
5. True
6. True
7. False
8. True
9. True
10. True
11. False
12. False
13. False
14. True
Knowledge Check
Question 1
Why do we need more scalable sorting algorithms than Bubble Sort for large input?
Question 2
What is divide and conquer?
Question 3
What is Merge Sort's base case?
Question 4
Why is the merge step linear?
Question 5
Why does Merge Sort become O(n log n)?
Question 6
What memory tradeoff does array-based Merge Sort commonly make?
Question 7
What is a Quick Sort pivot?
Question 8
What does partitioning accomplish?
Question 9
Why is Quick Sort often O(n log n) on average?
Question 10
How can Quick Sort become O(n²)?
Question 11
Which algorithm shown is stable?
Question 12
Why should textbook implementations not automatically replace Java's standard sorting APIs?
Knowledge Check Answers
Answer 1
Because quadratic work grows very quickly. Algorithms around O(n log n) scale much better as n becomes large।
Answer 2
Divide and conquer splits a larger problem into smaller subproblems, solves those smaller problems, and then combines or organizes the results into the final solution।
Answer 3
A range containing zero or one element is already sorted।
Answer 4
Two sorted ranges can be merged by advancing through them once, so each value is copied or considered only a constant number of times।
Answer 5
There are roughly O(log n) recursive split levels, and each level processes roughly O(n) total values during merging։
Therefore:
O(n × log n)
=
O(n log n)
Answer 6
It commonly uses:
O(n)
extra buffer memory to merge array ranges efficiently।
Answer 7
A pivot is the reference value used to divide the current Quick Sort range into regions according to their relationship with that value।
Answer 8
Partitioning rearranges a range around the pivot and places the pivot into an appropriate partition position so the resulting left and right regions can be recursively sorted।
Answer 9
With reasonably balanced partitions, recursion depth is around O(log n) while each level performs around O(n) partition work।
Answer 10
Repeatedly poor pivot choices can produce highly unbalanced partitions such as:
n - 1
and
0
causing quadratic total work।
Answer 11
The Merge Sort implementation shown can be stable।
The common Quick Sort implementation shown is not stable।
Answer 12
Production sorting implementations are heavily tested and optimized and may use hybrid strategies, specialized algorithms, better pivot handling, and other implementation details that textbook versions omit।
Merge Sort vs Quick Sort Summary
Merge Sort
Mental model:
Split
Sort halves
Merge
Time:
Best: O(n log n)
Average: O(n log n)
Worst: O(n log n)
Additional space:
O(n)
Typical stability:
Stable
Strengths:
Predictable complexity
Natural stable sorting
Clear divide-and-conquer structure
Tradeoff:
Additional memory
Quick Sort
Mental model:
Choose pivot
Partition
Sort both sides
Time:
Average:
O(n log n)
Worst:
O(n²)
Additional memory:
No full O(n) auxiliary array
but recursion uses stack space
Typical stability:
Not stable
Strengths:
Excellent practical array performance
Good memory characteristics
Strong locality
Tradeoff:
Performance depends on partition quality
Lesson Summary
এই lesson-এ আমরা quadratic sorting থেকে scalable divide-and-conquer sorting-এর দিকে এগিয়েছি।
We learned:
O(n²)sorting becomes expensive for large input- Divide and conquer breaks problems into smaller subproblems
- Merge Sort recursively divides ranges into halves
- Single-element ranges form the base case
- Sorted halves are combined using a linear merge operation
- Merge Sort runs in
O(n log n)in best, average, and worst cases - Array-based Merge Sort commonly requires
O(n)extra buffer space - Merge Sort can be stable
- Quick Sort selects a pivot
- Partitioning organizes a range around that pivot
- Recursive Quick Sort processes the regions on either side
- Quick Sort often performs around
O(n log n)on average - Poor pivot selection can cause
O(n²)worst-case behavior - Quick Sort usually does not require another full-size array
- Common in-place Quick Sort is not stable
- Pivot strategy significantly affects performance
- Production sorting algorithms use more sophisticated and often hybrid strategies
- Understanding textbook algorithms helps us reason about standard-library behavior without reinventing it in normal application code
The central distinction is:
Merge Sort
→ split first
→ merge later
Quick Sort
→ partition first
→ recurse later
And the most important engineering lesson is:
Algorithm performance comes from
how the problem shrinks,
how much work happens at each level,
and what additional memory is required.
Next Lesson
পরবর্তী lesson:
Java's Built-In Sorting and Searching APIs
আমরা শিখব:
Arrays.sort()- Primitive vs object array sorting
List.sort()Collections.sort()- Natural ordering
ComparableComparator- Comparator chaining
- Reversed ordering
- Sorting by multiple fields
Arrays.binarySearch()Collections.binarySearch()- Keeping sorting and searching order consistent
- When standard-library APIs should replace manual algorithms