# Implement Merge Sort using Java

If you’re in a computer science background, widening your technical horizons is the best thing you should do. However, your programming skills matter the most and one must continuously keep sharpening these skills. And to become a better programmer in the future. Though there are multiple things to focus on, one specific area you must focus on is the world of data structures. Data structures in general are specific approaches to solve problems in such a way that computer resources get used minimum. In general, there are multiple data structures you can learn and implement as well. However, to keep things simple were going to start with some mediocre programs you must learn before moving on to complex algorithms. Therefore today we’re going to learn how to Implement Binary Merge Sort using Java.

## What is Merge Sort?

**One of the very efficient sorting algorithms**in data structures.**Merge Sort is the way of arranging elements in a sequence or ascending order.**

- Merge sort
**follows the principles of the divide & conquer Algorithm**. The**base array is divided into two arrays. And is further divided**till the arrangement of**elements doesn’t form a sequence**.

**Also Read: ****Implement Binary Insertion Sort using Java**

## What’s The Approach?

- Firstly we’ll
**find the midpoint**of the array so**that we know from where to divide the array**.

- So let us
**consider the array,**

.So the**array[begin..mid..end]****first subarray**will be

and the**L[begin..mid]****second subarray**will be**R[mid+1..end]**

**The above instructions will be executed recursively**till**there’s only a single element**in the**subarray**.

**Once the elements are sorted**we’ll**merge both the subarrays**in ascending order.

**The above three instructions will continue to repeat till the entire array is sorted**.

## Java Program To Implement Merge Sort

**Input:**

**12, 11, 13, 5, 6, 7 **

**Output:**

**Sorted array is: **

**5 6 7 11 12 13**

/* Java program for Implementation of Merge Sort */ class MergeSort { // Merges two subarrays of arr[]. // First subarray is arr[l..m] // Second subarray is arr[m+1..r] void merge(int arr[], int l, int m, int r) { // Find sizes of two subarrays to be merged int n1 = m - l + 1; int n2 = r - m; /* Create temp arrays */ int L[] = new int[n1]; int R[] = new int[n2]; /*Copy data to temp arrays*/ for (int i = 0; i < n1; ++i) L[i] = arr[l + i]; for (int j = 0; j < n2; ++j) R[j] = arr[m + 1 + j]; /* Merge the temp arrays */ // Initial indexes of first and second subarrays int i = 0, j = 0; // Initial index of merged subarray array int k = l; while (i < n1 && j < n2) { if (L[i] <= R[j]) { arr[k] = L[i]; i++; } else { arr[k] = R[j]; j++; } k++; } /* Copy remaining elements of L[] if any */ while (i < n1) { arr[k] = L[i]; i++; k++; } /* Copy remaining elements of R[] if any */ while (j < n2) { arr[k] = R[j]; j++; k++; } } // Main function that sorts arr[l..r] using // merge() void sort(int arr[], int l, int r) { if (l < r) { // Find the middle point int m =l+ (r-l)/2; // Sort first and second halves sort(arr, l, m); sort(arr, m + 1, r); // Merge the sorted halves merge(arr, l, m, r); } } /* A utility function to print array of size n */ static void printArray(int arr[]) { int n = arr.length; for (int i = 0; i < n; ++i) System.out.print(arr[i] + " "); System.out.println(); } // Driver code public static void main(String args[]) { int arr[] = { 12, 11, 13, 5, 6, 7 }; System.out.println("Given Array"); printArray(arr); MergeSort obj = new MergeSort(); obj.sort(arr, 0, arr.length - 1); System.out.println("\nSorted array"); printArray(arr); } }