Merge Sort in Java
Merge Sort in Java : Detailed Explanation with Code
In this article, we will explore Merge Sort in Java programming. We will cover its working, algorithm, implementation, and complexity analysis.
Sorting is one of the most important operations in computer science and software development. It helps organize data and improve efficiency in many applications. Among the various sorting algorithms, Merge Sort stands out for its consistent performance and use of the divide and conquer strategy.

What is Merge Sort?
Merge Sort is a divide and conquer algorithm.
- It works by dividing the array into smaller subarrays, sorting them individually, and then merging them to produce a sorted array.
- Merge Sort was invented by John von Neumann in 1945. It is known for its stable sorting behavior and predictable performance, even in worst case scenarios.
How Merge Sort Works ?
Merge Sort works in three main steps:
- Divide: Split the array into two halves recursively.
- Conquer: Sort each half recursively.
- Merge: Combine the sorted halves into one sorted array.
Recursion continues until each subarray has only one element. Then, it merges the sorted parts one by one.
Algorithm of Merge Sort
Here’s a step by step breakdown of the Merge Sort algorithm:
1. If the array has more than one element:
- Find the middle index of the array.
- Divide the array into two halves: left and right.
- Recursively call Merge Sort on both halves.
- Merge the sorted halves.
2. If the array has only one element, it is already sorted.
Pseudocode:
mergeSort(arr, left, right) if left < right mid = (left + right) / 2 mergeSort(arr, left, mid) mergeSort(arr, mid + 1, right) merge(arr, left, mid, right)


Implementation of Merge Sort in Java Programming
Code:
public class MergeSort { // Function to sort the array using merge sort public void mergeSort(int[] arr, int left, int right) { if (left < right) { // Find the middle point int mid = left + (right - left) / 2; // Sort first and second halves mergeSort(arr, left, mid); mergeSort(arr, mid + 1, right); // Merge the sorted halves merge(arr, left, mid, right); } } // Function to merge two subarrays of arr[] public void merge(int[] arr, int left, int mid, int right) { // Find sizes of two subarrays to be merged int n1 = mid - left + 1; int n2 = right - mid; // Create temp arrays int[] leftArray = new int[n1]; int[] rightArray = new int[n2]; // Copy data to temp arrays 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]; // Merge the temp arrays int i = 0, j = 0; int k = left; while (i < n1 && j < n2) { if (leftArray[i] <= rightArray[j]) { arr[k] = leftArray[i]; i++; } else { arr[k] = rightArray[j]; j++; } k++; } // Copy remaining elements of leftArray while (i < n1) { arr[k] = leftArray[i]; i++; k++; } // Copy remaining elements of rightArray while (j < n2) { arr[k] = rightArray[j]; j++; k++; } } // Utility method to print the array public void printArray(int[] arr) { for (int value : arr) System.out.print(value + " "); System.out.println(); } // Main method to test the algorithm public static void main(String[] args) { MergeSort ms = new MergeSort(); int[] arr = { 12, 11, 13, 5, 6, 7 }; System.out.println("Original array:"); ms.printArray(arr); ms.mergeSort(arr, 0, arr.length - 1); System.out.println("Sorted array:"); ms.printArray(arr); } }
Explanation of the Merge Sort Code:
- mergeSort() – This is the main recursive method. It splits the array and calls itself on both halves.
- merge() – This method merges two sorted subarrays. It uses temporary arrays to store elements during merging.
- printArray() – A utility function to display the array.
- main() – This method sets up an example array, applies merge sort, and prints the results.
Average Case: O(n log n)
Worst Case: O(n log n)


Program for Merge Sort in Java
In Java, there are two common ways to implement the Merge Sort algorithm.
Both methods follow the same core logic of divide and conquer, but they differ slightly in how they handle the arrays during the merging process:
- Method 1: Using Two Separate Subarrays:
- In this method, we create two temporary subarrays, one for the left half and one for the right half of the main array.
- These subarrays are used to hold the elements before merging them back in sorted order. This method makes the merging step clearer and easier to follow, especially for beginners.
- Method 2: Using a Single Array with Index Ranges
- This variation performs the same operations, but instead of creating two separate subarrays, it works with a single array by tracking the start and end indices.
- This helps reduce some overhead in terms of copying data, but the logic can be a bit more complex.
Space complexity is the same i.e. O(n) in both cases as even though there are two subarrays in method 1 they in total have n array items and method 2 also with one single array also has n array items.
//Java Program for Merge Sort class Main { // this function display the array public static void display(int[] arr, int size) { for(int i = 0; i < size; i++) { System.out.print(arr[i] + " "); } System.out.println(); } // main function of the program public static void main(String[] args) { int[] a = {12, 8, 4, 14, 36, 64, 15, 72, 67, 84}; int size = a.length; display(a, size); mergeSort(a, 0, size - 1); display(a, size); } // this function apply merging and sorting in the array static void mergeSort(int[] a, int left, int right) { int mid; if(left < right) { // can also use mid = left + (right - left) / 2 // this can avoid data type overflow mid = (left + right) / 2; // recursive calls to sort first half and second half sub-arrays mergeSort(a, left, mid); mergeSort(a, mid + 1, right); merge(a, left, mid, right); } } // after sorting this function merge the array static void merge(int[] arr, int left, int mid, int right) { int i, j, k; int n1 = mid - left + 1; int n2 = right - mid; // create temp arrays to store left and right sub-arrays int L[] = new int[n1]; int R[] = new int[n2]; // Copying data to temp arrays L[] and R[] for (i = 0; i < n1; i++) L[i] = arr[left + i]; for (j = 0; j < n2; j++) R[j] = arr[mid + 1 + j]; // here we merge the temp arrays back into arr[l..r] i = 0; // Starting index of L[i] j = 0; // Starting index of R[i] k = left; // Starting index of merged sub-array while (i < n1 && j < n2) { // place the smaller item at arr[k] pos if (L[i] <= R[j]) { arr[k] = L[i]; i++; } else { arr[k] = R[j]; j++; } k++; } // Copy the remaining elements of L[], if any while (i < n1) { arr[k] = L[i]; i++; k++; } // Copy the remaining elements of R[], if any while (j < n2) { arr[k] = R[j]; j++; k++; } } }
Output
12 8 4 14 36 64 15 72 67 84 4 8 12 14 15 36 64 67 72 84
//Java Program for Merge Sort class Main { // this function display the array public static void display(int[] arr, int size) { for(int i = 0; i < size; i++) { System.out.print(arr[i] + " "); } System.out.println(); } // main function of the program public static void main(String[] args) { int[] a = {12, 8, 4, 14, 36, 64, 15, 72, 67, 84}; int size = a.length; display(a, size); mergeSort(a, 0, size - 1); display(a, size); } // this function apply merging and sorting in the array static void mergeSort(int[] a, int left, int right) { int mid; if(left < right) { // can also use mid = left + (right - left) / 2 // this can avoid data type overflow mid = (left + right) / 2; // recursive calls to sort first half and second half sub-arrays mergeSort(a, left, mid); mergeSort(a, mid + 1, right); merge(a, left, mid, right); } } // after sorting this function merge the array static void merge(int[] a, int left, int mid, int right) { int i = left; // starting index of left sub-array int j = mid + 1; // starting index of right sub-array int index = left; // used to place items in temp[] int[] temp = new int[10]; while(i <= mid && j <= right) { // place the smaller item at temp[index] if(a[i] < a[j]) { temp[index] = a[i]; i = i + 1; } else { temp[index] = a[j]; j = j + 1; } index++; } // i > mid would mean all items for left // sub-array were successfully placed, and there // must be unplaced right sub-array items if(i > mid) { while(j <= right) { temp[index] = a[j]; index++; j++; } } else { while(i <= mid) { temp[index] = a[i]; index++; i++; } } int p = left; while(p < index) { a[p] = temp[p]; p++; } } }
Output
12 8 4 14 36 64 15 72 67 84 4 8 12 14 15 36 64 67 72 84
Advantages of Merge Sort
- Stable Sort – It maintains the order of equal elements.
- Predictable Performance – Always runs in O(n log n) time.
- Useful for Linked Lists – Does not require random access.
- Efficient for Large Data – Performs better than bubble or insertion sort on large datasets.
Disadvantages of Merge Sort
- Uses Extra Space – Not ideal for memory constrained systems.
- Slower on Small Data – For small arrays, insertion sort can be faster.
- Complex Implementation – More complex than simple sorting methods.
Conclusion
Merge Sort is a powerful and efficient sorting algorithm based on the divide and conquer principle. Its predictable O(n log n) time complexity makes it a great choice for sorting large arrays and linked lists.
Although it uses extra space, its stability and consistent performance give it an edge over some other algorithms.

FAQ's related to Merge Sort in Java
Answer:
Merge Sort is based on the divide and conquer technique. It splits the array into halves, recursively sorts them, and merges the sorted halves to produce the final sorted array.
Answer:
No, Merge Sort is not in-place. It uses extra space for temporary arrays during the merge process, which leads to a space complexity of O(n).
Answer:
Merge Sort maintains the relative order of equal elements while merging, which makes it stable. This is important when sorting records with multiple fields (like name and age).
Answer:
Merge Sort has a time complexity of O(n log n) in the best, average, and worst cases, making it very predictable and efficient even for large datasets.
Answer:
Merge Sort is preferred when stability is required or when dealing with linked lists. It is also a better choice in worst case scenarios where Quick Sort can degrade to O(n²).
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment