Sorting Algorithms in Java: Bubble, Selection, Insertion, Merge, and Quick Sort
Chapter 4: Merge Sort in Java
1. Description of Merge Sort (No Coding)
Merge Sort is a divide-and-conquer sorting algorithm
that recursively splits an array into smaller subarrays, sorts them
individually, and then merges them back together in sorted order.
It is much faster than Bubble Sort, Selection Sort,
and Insertion Sort, especially for large datasets, because it runs in O(n
log n) time complexity in all cases. However, it requires additional memory
space of O(n).
Working Principle of Merge Sort
- Divide
– Split the array into two equal (or nearly equal) halves.
- Conquer
– Recursively sort both halves.
- Merge
– Combine the sorted halves into a single sorted array.
Visualization Example
Unsorted Array:
[8, 3, 5, 2, 9, 4, 1, 7]
Step 1: Divide the array into two halves
[8, 3, 5, 2] | [9, 4, 1, 7]
Step 2: Recursively divide further
[8, 3] | [5, 2] | [9, 4] | [1, 7]
Step 3: Recursively sort & merge back
- [8,
3] → [3, 8]
- [5,
2] → [2, 5]
- [9,
4] → [4, 9]
- [1,
7] → [1, 7]
Step 4: Merge sorted subarrays
- [3,
8] & [2, 5] → [2, 3, 5, 8]
- [4,
9] & [1, 7] → [1, 4, 7, 9]
Step 5: Merge final halves
- [2,
3, 5, 8] & [1, 4, 7, 9] → Final sorted array: [1, 2, 3, 4, 5,
7, 8, 9]
2. Merge Sort Coding Examples
(a) Syllabus-Based Example (Sorting an array of numbers)
public
class MergeSortExample {
static void mergeSort(int arr[], int left,
int right) {
if (left < right) {
int mid = (left + right) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
static void merge(int arr[], int left, int
mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int leftArray[] = new int[n1];
int rightArray[] = new int[n2];
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];
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++;
}
while (i < n1) {
arr[k] = leftArray[i];
i++;
k++;
}
while (j < n2) {
arr[k] = rightArray[j];
j++;
k++;
}
}
public static void main(String args[]) {
int arr[] = {8, 3, 5, 2, 9, 4, 1, 7};
mergeSort(arr, 0, arr.length - 1);
System.out.println(java.util.Arrays.toString(arr));
}
}
Output:
[1, 2, 3, 4, 5, 7, 8, 9]
(b) Real-World Example (Sorting student names
alphabetically)
import
java.util.Arrays;
public
class MergeSortStrings {
static void mergeSort(String arr[], int
left, int right) {
if (left < right) {
int mid = (left + right) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
static void merge(String arr[], int left,
int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
String leftArray[] = new String[n1];
String rightArray[] = new String[n2];
System.arraycopy(arr, left, leftArray,
0, n1);
System.arraycopy(arr, mid + 1,
rightArray, 0, n2);
int i = 0, j = 0, k = left;
while (i < n1 && j < n2)
{
if
(leftArray[i].compareTo(rightArray[j]) <= 0) {
arr[k] = leftArray[i];
i++;
} else {
arr[k] = rightArray[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = leftArray[i];
i++;
k++;
}
while (j < n2) {
arr[k] = rightArray[j];
j++;
k++;
}
}
public static void main(String args[]) {
String students[] =
{"Charlie", "Alice", "Bob", "David",
"Eve"};
mergeSort(students, 0, students.length
- 1);
System.out.println(Arrays.toString(students));
}
}
Output:
[Alice, Bob, Charlie, David, Eve]
3. Advantages of Merge Sort (Pros)
✔ Time complexity is O(n log
n) in all cases – Performs well on large datasets.
✔ Stable sorting algorithm – Maintains
relative order of duplicate values.
✔ Good for linked lists – Works well for
sorting linked lists due to efficient merging.
✔ Parallelizable – Can be efficiently
implemented using multithreading.
✔ Performs well on external sorting – Useful
for sorting large datasets stored on disk.
4. Disadvantages of Merge Sort (Cons)
❌ Requires extra memory of
O(n) – Uses additional space for merging.
❌
Not in-place sorting – Unlike Quick Sort, it needs extra arrays.
❌
More recursive function calls – Leads to overhead in memory.
❌
Slower than Quick Sort for random data – Quick Sort is usually faster in
practice.
❌
Not suitable for small arrays – Insertion Sort performs better for n
< 50.
5. How is Merge Sort Better Than Other Sorting
Techniques?
- Faster
than Bubble Sort, Selection Sort, and Insertion Sort for large
datasets.
- Guaranteed
O(n log n) complexity – No worst-case degradation like Quick Sort.
- Stable
sorting algorithm – Maintains order of duplicate elements.
- Best
for linked lists and external sorting – Efficient when sorting huge
datasets.
- Better
than Quick Sort for worst-case scenarios – Quick Sort degrades to
O(n²), while Merge Sort stays at O(n log n).
6. Best Cases to Use Merge Sort
✔ When sorting linked lists
– Efficient merging.
✔ When stability is required – Maintains order
of duplicates.
✔ For large datasets – Performs well on
large-scale sorting.
✔ For external sorting (e.g., files on disk) –
Handles large datasets efficiently.
7. Worst Cases to Use Merge Sort
❌ When memory usage is a
concern – Requires O(n) extra space.
❌
For small datasets – Insertion Sort is more efficient.
❌
When in-place sorting is required – Quick Sort is better in such cases.
Final Thoughts
Merge Sort is one of the most efficient sorting
algorithms, especially for large datasets. However, it requires extra
memory and is not as fast as Quick Sort for random data. 🚀
FAQs
Why is Bubble Sort considered inefficient for large datasets?
Bubble Sort repeatedly compares adjacent elements and swaps
them if they are in the wrong order. This leads to O(n²) time complexity,
making it highly inefficient for large datasets. The excessive number of swaps
and comparisons makes it slow compared to Merge Sort (O(n log n)) or Quick
Sort (O(n log n)).
2. Why is Quick Sort preferred over Merge Sort in many practical applications?
Quick Sort is preferred in many scenarios because:
- It
has O(n log n) average-case time complexity, which is comparable to
Merge Sort.
- It
sorts in-place, meaning it requires O(log n) space on
average, whereas Merge Sort requires O(n) extra space.
- Quick
Sort has better cache performance due to its partitioning approach.
However, in the worst case (O(n²)), Quick Sort can be inefficient, while Merge Sort always guarantees O(n log n) time.
3. Which sorting algorithm is best for nearly sorted data and why?
Insertion Sort is best for nearly sorted data
because:
- It
runs in O(n) time when the array is nearly sorted.
- It
requires only a few swaps and comparisons to sort such an array.
- Unlike
Bubble Sort, it does not perform unnecessary swaps, making it
faster in practice for small and nearly sorted datasets.
4. What is a stable sorting algorithm, and which algorithms in our list are stable?
A sorting algorithm is stable if it preserves the
relative order of elements with equal values.
Stable sorting algorithms in our list:
✅
Bubble Sort
✅
Insertion Sort
✅
Merge Sort
🚫
Selection Sort (can swap elements with the same value)
🚫
Quick Sort (depends on implementation)
5. Can we optimize Bubble Sort? How?
Yes! We can optimize Bubble Sort by introducing a swap
flag:
- If
in a complete pass, no swaps occur, the array is already sorted.
- This
reduces the best-case time complexity to O(n) instead of O(n²).
Optimized Bubble Sort in Java:
static
void optimizedBubbleSort(int arr[]) {
int n = arr.length;
boolean swapped;
for (int i = 0; i < n - 1; i++) {
swapped = false;
for (int j = 0; j < n - i - 1; j++)
{
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
if (!swapped) break; // Stop if already sorted
}
}
This optimization improves performance significantly when
the input is partially sorted.
6. Why does Quick Sort have an O(n²) worst-case time complexity?
Quick Sort's worst-case occurs when:
- The smallest
or largest element is always chosen as the pivot.
- The
array is already sorted in ascending or descending order, and no
balanced partitioning occurs.
- This
results in T(n) = T(n-1) + O(n) → O(n²) time complexity.
To avoid this, randomized pivot selection or choosing
the median pivot is recommended.
7. How does Merge Sort work in a linked list, and why is it better than Quick Sort for linked lists?
Merge Sort is preferred for linked lists because:
- It
does not require random access to elements.
- It
sorts efficiently in O(n log n) time, even without additional space
(in recursive implementations).
- Quick
Sort requires frequent swapping, which is expensive in linked lists.
8. Why is Selection Sort not a stable algorithm? Can it be made stable?
Selection Sort is not stable because:
- It
swaps the minimum element with the first unsorted element, which may move
an equal-value element before another occurrence of the same value.
- Example:
Sorting [(A, 3), (B, 3), (C, 2)] using Selection Sort can place (B, 3)
before (A, 3), changing their original order.
To make it stable, we can modify Selection Sort by
using linked lists or keeping track of indexes instead of swapping values
directly.
9. Why does Merge Sort require extra space, and how can it be optimized?
Merge Sort requires O(n) extra space because:
- It
uses temporary arrays to merge two halves.
- Each
recursive call needs new storage for merged subarrays.
Optimizations to reduce space:
- Use in-place
Merge Sort, but this makes merging more complex (using extra swaps
instead of new arrays).
- Use Iterative
Merge Sort, which reduces recursion stack overhead.
10. Can sorting be done in O(n) time? If yes, how?
Yes, sorting can be done in O(n) time, but only for special
cases, such as:
- Counting
Sort - When the range of numbers is small (O(n+k)).
- Radix
Sort - If numbers have a limited number of digits (O(d * (n + b))
where b is the base and d is the number of digits).
- Bucket
Sort - When input data is uniformly distributed (O(n) in best cases).
These non-comparison sorts work by categorizing elements
into buckets instead of using comparisons (O(n log n) is the lower bound
for comparison-based sorts).
Comments(0)