# Implementing Merge Sort in Java

13

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 ``````