If you are learning Java, understanding sorting algorithms is an important step toward becoming a skilled programmer. Sorting is used in almost every software application, whether it’s organizing a list of names, displaying search results, or managing large datasets efficiently. Merge Sort is one of the most reliable and widely-used sorting techniques because it can handle large amounts of data with consistent performance.
with hands-on learning.
get the skills and confidence to land your next move.
Merge Sort follows a divide-and-conquer approach, meaning it splits a big problem into smaller, manageable pieces, solves each piece, and then combines them to form the final sorted list. Learning Merge Sort not only helps you sort data efficiently but also strengthens your understanding of recursion and algorithmic thinking. In this article, we will explore multiple ways to implement Merge Sort in Java, making it easy for beginners to understand and apply.
Program 1: Merge Sort Using Recursion
The first approach shows the classic recursive implementation of Merge Sort. It splits the array into halves, sorts each half recursively, and then merges them back together in order.
public class MergeSortRecursive {
public static void mergeSort(int[] array) {
if (array.length <= 1) return;
int mid = array.length / 2;
int[] left = new int[mid];
int[] right = new int[array.length - mid];
System.arraycopy(array, 0, left, 0, mid);
System.arraycopy(array, mid, right, 0, array.length - mid);
mergeSort(left);
mergeSort(right);
merge(array, left, right);
}
private static void merge(int[] array, int[] left, int[] right) {
int i = 0, j = 0, k = 0;
while (i < left.length && j < right.length) {
if (left[i] < right[j]) {
array[k++] = left[i++];
} else {
array[k++] = right[j++];
}
}
while (i < left.length) array[k++] = left[i++];
while (j < right.length) array[k++] = right[j++];
}
public static void main(String[] args) {
int[] numbers = {38, 27, 43, 3, 9, 82, 10};
System.out.println("Original Array: ");
for (int num : numbers) System.out.print(num + " ");
mergeSort(numbers);
System.out.println("\nSorted Array: ");
for (int num : numbers) System.out.print(num + " ");
}
}In this program, the array is divided into smaller parts until each part has one element. Then, the merge function combines the smaller arrays back into a single sorted array. This recursive approach is useful because it efficiently handles large arrays and teaches beginners the fundamentals of recursion.
Program 2: Merge Sort with Separate Merge Function
In this program, the merge logic is separated into its own method, making the code more modular and readable. It helps beginners understand the role of merging two sorted arrays.
public class MergeSortWithHelper {
public static int[] mergeSort(int[] array) {
if (array.length <= 1) return array;
int mid = array.length / 2;
int[] left = mergeSort(java.util.Arrays.copyOfRange(array, 0, mid));
int[] right = mergeSort(java.util.Arrays.copyOfRange(array, mid, array.length));
return merge(left, 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;
}
public static void main(String[] args) {
int[] numbers = {12, 11, 13, 5, 6, 7};
System.out.println("Original Array: " + java.util.Arrays.toString(numbers));
numbers = mergeSort(numbers);
System.out.println("Sorted Array: " + java.util.Arrays.toString(numbers));
}
}By separating the merge method, the program becomes more organized. Beginners can clearly see how two sorted arrays are combined, which simplifies understanding the recursive structure and improves code readability.
Program 3: Iterative Merge Sort
While Merge Sort is naturally recursive, it can also be implemented using loops. This iterative approach is useful for large arrays where recursion may hit memory limits.
public class MergeSortIterative {
public static void mergeSort(int[] array) {
int n = array.length;
int[] temp = new int[n];
for (int size = 1; size < n; size *= 2) {
for (int leftStart = 0; leftStart < n; leftStart += 2 * size) {
int mid = Math.min(leftStart + size, n);
int rightEnd = Math.min(leftStart + 2 * size, n);
merge(array, temp, leftStart, mid, rightEnd);
}
}
}
private static void merge(int[] array, int[] temp, int leftStart, int mid, int rightEnd) {
int i = leftStart, j = mid, k = leftStart;
while (i < mid && j < rightEnd) {
if (array[i] <= array[j]) temp[k++] = array[i++];
else temp[k++] = array[j++];
}
while (i < mid) temp[k++] = array[i++];
while (j < rightEnd) temp[k++] = array[j++];
System.arraycopy(temp, leftStart, array, leftStart, rightEnd - leftStart);
}
public static void main(String[] args) {
int[] numbers = {20, 3, 15, 7, 9};
System.out.println("Original Array: " + java.util.Arrays.toString(numbers));
mergeSort(numbers);
System.out.println("Sorted Array: " + java.util.Arrays.toString(numbers));
}
}In this iterative version, the array is merged in pairs of increasing size until the whole array is sorted. Beginners can appreciate this approach as it avoids recursion and shows that algorithms can often be implemented in multiple ways.
Program 4: Merge Sort in Descending Order
This program demonstrates a small modification to sort an array in descending order by changing the comparison logic.
public class MergeSortDescending {
public static int[] mergeSortDescending(int[] array) {
if (array.length <= 1) return array;
int mid = array.length / 2;
int[] left = mergeSortDescending(java.util.Arrays.copyOfRange(array, 0, mid));
int[] right = mergeSortDescending(java.util.Arrays.copyOfRange(array, mid, array.length));
return mergeDescending(left, right);
}
private static int[] mergeDescending(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;
}
public static void main(String[] args) {
int[] numbers = {4, 10, 2, 8, 6};
System.out.println("Original Array: " + java.util.Arrays.toString(numbers));
numbers = mergeSortDescending(numbers);
System.out.println("Sorted Array in Descending Order: " + java.util.Arrays.toString(numbers));
}
}By changing the comparison from < to >, the array is sorted in descending order. This shows beginners how small tweaks can change the behavior of an algorithm, offering flexibility in real-world applications.
Program 5: Merge Sort Using Generics
Java allows us to implement Merge Sort using generics, enabling sorting of different data types like integers, doubles, or strings.
public class MergeSortGeneric {
public static <T extends Comparable<T>> T[] mergeSort(T[] array) {
if (array.length <= 1) return array;
int mid = array.length / 2;
T[] left = java.util.Arrays.copyOfRange(array, 0, mid);
T[] right = java.util.Arrays.copyOfRange(array, mid, array.length);
return merge(mergeSort(left), mergeSort(right));
}
private static <T extends Comparable<T>> T[] merge(T[] left, T[] right) {
T[] result = java.util.Arrays.copyOf(left, left.length + right.length);
int i = 0, j = 0, k = 0;
while (i < left.length && j < right.length) {
if (left[i].compareTo(right[j]) <= 0) 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;
}
public static void main(String[] args) {
String[] words = {"banana", "apple", "cherry", "date"};
System.out.println("Original Array: " + java.util.Arrays.toString(words));
words = mergeSort(words);
System.out.println("Sorted Array: " + java.util.Arrays.toString(words));
}
}Using generics makes Merge Sort flexible and reusable for multiple data types. Beginners can see how type constraints in Java help write safe and versatile code, a useful skill for larger projects.
Program 6: Merge Sort on Linked Lists
Merge Sort isn’t limited to arrays; it can also be used to sort linked lists efficiently. Since linked lists are naturally divided into nodes, splitting and merging them is simple and memory-efficient.
public class MergeSortLinkedList {
Node head;
public Node sortedMerge(Node a, Node b) {
Node result = null;
if (a == null)
return b;
if (b == null)
return a;
if (a.data <= b.data) {
result = a;
result.next = sortedMerge(a.next, b);
} else {
result = b;
result.next = sortedMerge(a, b.next);
}
return result;
}
public Node getMiddle(Node h) {
if (h == null)
return h;
Node slow = h, fast = h.next;
while (fast != null) {
fast = fast.next;
if (fast != null) {
slow = slow.next;
fast = fast.next;
}
}
return slow;
}
public Node mergeSort(Node h) {
if (h == null || h.next == null)
return h;
Node middle = getMiddle(h);
Node nextOfMiddle = middle.next;
middle.next = null;
Node left = mergeSort(h);
Node right = mergeSort(nextOfMiddle);
return sortedMerge(left, right);
}
void printList(Node headref) {
while (headref != null) {
System.out.print(headref.data + " ");
headref = headref.next;
}
}
public static void main(String[] args) {
MergeSortLinkedList list = new MergeSortLinkedList();
list.head = new Node(15);
list.head.next = new Node(10);
list.head.next.next = new Node(5);
list.head.next.next.next = new Node(20);
list.head.next.next.next.next = new Node(3);
list.head.next.next.next.next.next = new Node(2);
System.out.println("Linked List before sorting:");
list.printList(list.head);
list.head = list.mergeSort(list.head);
System.out.println("\nLinked List after sorting:");
list.printList(list.head);
}
}
class Node {
int data;
Node next;
Node(int d) {
data = d;
next = null;
}
}In this program, we use the same divide-and-conquer idea but apply it to linked lists. The list is divided into two halves using a slow and fast pointer technique, then both halves are sorted recursively and merged back together. This version is often preferred for linked lists because it doesn’t need extra space like the array-based version. It’s efficient and shows how flexible the Merge Sort algorithm really is.
Frequently Asked Questions (FAQ)
Sorting arrays with Merge Sort often brings up common questions. Here are some key answers for beginners.
Q1: What is the time complexity of Merge Sort?
Merge Sort has a time complexity of O(n log n) in best, average, and worst cases, making it more efficient than simpler sorting methods like bubble sort for large datasets.
Q2: Is Merge Sort a stable sorting algorithm?
Yes, Merge Sort is stable, meaning it preserves the relative order of equal elements, which is important when sorting complex data.
Q3: Can Merge Sort work with linked lists?
Absolutely. Merge Sort is efficient for linked lists because merging can be done without extra space, unlike arrays.
Q4: How does Merge Sort compare to Quick Sort?
Merge Sort is stable and guarantees O(n log n) performance, while Quick Sort can be faster on average but is not stable and may degrade to O(n²) in the worst case.
Q5: Can Merge Sort be implemented iteratively?
Yes. Iterative Merge Sort avoids recursion and is suitable for very large arrays where recursion depth could cause issues.
Conclusion
Merge Sort is a fundamental algorithm that every Java programmer should learn. By mastering Merge Sort, you understand recursion, loops, and how to handle large datasets efficiently. In this article, we explored multiple approaches, including recursive, iterative, descending order, and generic implementations.
For beginners, the best way to grasp Merge Sort is to practice writing it yourself, experiment with different data types, and try modifying it for ascending or descending order. Sorting is a core skill, and learning Merge Sort will provide a strong foundation for more advanced programming challenges.
