There are different sorting algorithms are available like selection sort, insertion sort etc. In this article we learn about one of them sorting algorithm, working of this sorting algorithm and example of this sorting algorithm. Merge sort algorithm is the simplest sorting algorithm as compare to other sorting algorithms.

The Merge sorting algorithm can be used to sorting a collection of objects. Merge sort is a so called divide and conquer algorithm. Divide and conquer algorithms divide the original data into smaller sets of data to solve the problem.

Algorithm:

Step 1 − if it is only one element in the list it is already sorted, return.
Step 2 − divide the list recursively into two halves until it can no more be divided.
Step 3 − merge the smaller lists into new list in sorted order.

Program: Java program for Merge Sort

In the following program we pass the integer array of numbers for sorting. Before sorting array int arr looks like {12, 11, 13, 5, 6, 7} and after performing merge sorting array of integers looks like {5, 6, 7, 11, 12, 13}

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)
{

int n1 = m - l + 1;
int n2 = r - m;
int L[] = new int [n1]; 
int R[] = new int [n2]; 

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];

int i = 0, j = 0; // Initial index of merged subarry 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++; 
} 
 while (i < n1) 
{ 
arr[k] = L[i]; 
i++; 
k++; 
} 
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}

void sort(int arr[], int l, int r)
{
if (l < r)
{

int m = (l+r)/2;
// Sort first and second halves
sort(arr, l, m);
sort(arr , m+1, r);
// Merge the sorted halves
merge(arr, l, m, r);
}
}
static void printArray(int arr[])
{
int n = arr.length;
for (int i=0; i<n; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}
public static void main(String args[])
{
int arr[] = {12, 11, 13, 5, 6, 7};
System.out.println("Given Array");
printArray(arr);
MergeSort ob = new MergeSort();
ob.sort(arr, 0, arr.length-1);
System.out.println("\nSorted array");
printArray(arr);
}
}

Output:

Given array is
12 11 13 5 6 7
Sorted array is
5 6 7 11 12 13
Merge Sort Program

Other than the merge sorting we write the articles for other sorting algorithms which are available in programming like Insertion sort, bubble sort. If you want to learn about them then see below articles. Learn about bubble sort see this article Bubble Sort. If you want to learn Insertion sort, quick sort, selection sort then see this article Insertion SortQuick sortSelection sort.

I hope you would like this article of sorting. If you face any difficulty or you are having any query then comment me I will definitely try to respond you…

Leave a Reply

Your email address will not be published. Required fields are marked *

Back to Top