# Implementing Merge Sort in Java

8
Advertisement

Implementing Merge Sort in Java

Merge Sort is a powerful and efficient sorting algorithm based on the divide-and-conquer technique. In this blog post, we’ll delve into the Implementing Merge Sort in Java, understand its algorithmic approach. Let’s explore how Merge Sort achieves a time complexity of O(n log n) and provides a stable and consistent performance.

## Understanding the Divide-and-Conquer Approach:

Merge Sort operates on the principle of divide and conquer, breaking down a problem into smaller sub-problems until they become trivial to solve. The algorithm then combines the solutions of the sub-problems to solve the original problem. In the case of sorting, Merge Sort recursively divides an array into halves until each sub-array contains only one element. It then merges these sorted sub-arrays to produce a fully sorted array.

Steps:

### Divide:

• Divide the unsorted array into two halves.

### Conquer:

• Recursively apply Merge Sort to each of the sub-arrays.

### Combine:

• Merge the two sorted sub-arrays into a single sorted array.

## Merge Sort Implementation in Java:

Java Program – Merge Sort
``````public class Main {

// Main method to sort the array using merge sort
public static void sort(int[] array) {
if (array == null || array.length <= 1) {
return; // Already sorted or empty array
}

// Call the mergeSort method to start the sorting process
mergeSort(array, 0, array.length - 1);
}

// Recursive method to divide the array and merge the sorted halves
private static void mergeSort(int[] array, int left, int right) {
if (left < right) {
// Find the middle point to divide the array into two halves
int mid = left + (right - left) / 2;

// Recursively sort the first and second halves
mergeSort(array, left, mid);
mergeSort(array, mid + 1, right);

// Merge the sorted halves
merge(array, left, mid, right);
}
}

// Merge method to combine two sorted halves into a single sorted array
private static void merge(int[] array, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;

// Create temporary arrays to store the left and right halves
int[] leftArray = new int[n1];
int[] rightArray = new int[n2];

// Copy data to temporary arrays
System.arraycopy(array, left, leftArray, 0, n1);
System.arraycopy(array, mid + 1, rightArray, 0, n2);

// Merge the two halves
int i = 0, j = 0, k = left;

while (i < n1 && j < n2) {
if (leftArray[i] <= rightArray[j]) {
array[k++] = leftArray[i++];
} else {
array[k++] = rightArray[j++];
}
}

// Copy remaining elements from leftArray, if any
while (i < n1) {
array[k++] = leftArray[i++];
}

// Copy remaining elements from rightArray, if any
while (j < n2) {
array[k++] = rightArray[j++];
}
}

// Helper method to print an array
public static void printArray(int[] array) {
for (int value : array) {
System.out.print(value + " ");
}
System.out.println();
}

// Example usage
public static void main(String[] args) {
int[] array = {38, 27, 43, 3, 9, 82, 10};

System.out.println("Original Array:");
printArray(array);

sort(array);

System.out.println("Sorted Array:");
printArray(array);
}
}
``````

## Explanation:

1. `sort` Method:
• This is the entry point to the Merge Sort algorithm. It checks if the array is null or has only one element (already sorted), and then calls `mergeSort` to begin the sorting process.
2. `mergeSort` Method:
• The recursive method that divides the array into halves until each sub-array contains one element. It then calls the `merge` method to merge the sorted sub-arrays.
3. `merge` Method:
• Merges two sorted halves (`leftArray` and `rightArray`) into a single sorted array (`array`).
• Uses three pointers (`i`, `j`, and `k`) to iterate through the left, right, and merged arrays.
4. `printArray` Method:
• A helper method to print the contents of an array.

### Example:

Consider the array `{38, 27, 43, 3, 9, 82, 10}`.

1. Initial Step:
• Array: `{38, 27, 43, 3, 9, 82, 10}`.
2. Recursive Steps:
• `{38, 27, 43}` and `{3, 9, 82, 10}`.
• Further divisions until each sub-array has one element.
3. Merging Steps:
• Merge sorted sub-arrays into larger sorted arrays.
4. Final Sorted Array:
• `{3, 9, 10, 27, 38, 43, 82}`.

This example illustrates how Merge Sort recursively divides and conquers the array, ultimately producing a fully sorted result.

Output:

Output – Merge Sort
``````Original Array:
38 27 43 3 9 82 10
Sorted Array:
3 9 10 27 38 43 82 ``````

### Advantages of Merge Sort:

• Stable Sorting: Maintains the relative order of equal elements.
• Predictable Performance: Consistently performs at O(n log n), making it suitable for large datasets.
• External Sorting: Can efficiently handle large datasets stored on external storage devices.

### Conclusion:

Merge Sort stands as a testament to the elegance and efficiency of divide-and-conquer algorithms. Its ability to consistently deliver a stable and optimal performance makes it a reliable choice for a variety of applications. In Java, the implementation is concise yet powerful, showcasing the beauty of the algorithm. As you delve deeper into the world of sorting algorithms, Merge Sort undoubtedly earns its place as a fundamental and reliable tool in the programmer’s toolkit.

Latest Posts: