Saturday, 12 June 2021

Merge sorting with example and program

Merge sort is a divide-and-conquer algorithm based on the idea of breaking down a list into several sub-lists until each sublist consists of a single element and merging those sub-lists in a manner that results into a sorted list.
Sorting by merging is a recursive, divide-and-conquer strategy. In the base case, we have a sequence with exactly one element in it. Since such a sequence is already sorted, there is nothing to be done. To sort a sequence of n>1 elements:

1. Divide the sequence into two sequences of length [n/2] and [n/2]

2. Recursively sort each of the two sub sequences; and then

3. Merge the sorted sub sequence to obtain the final result.



class MergeSort
{ int[] a;
int[] tmp;
MergeSort(int[] arr)
{ a = arr;
tmp = new int[a.length];
void msort()
{ sort(0, a.length-1); }
void sort(int left, int right)
if(left < right)
int mid =(left+right)/2;
sort(left, mid);
sort(mid+1, right);
merge(left, mid, right);
void merge(int left, int mid, int right)
{ int i = left;
int j = left;
int k = mid+1;
while( j<= mid && k <= right )
if(a[j] < a[k])
tmp[i++] = a[j++];
tmp[i++] = a[k++];
while( j <= mid )
tmp[i++] = a[j++];
for(i=left; i < k; i++)
a[i] = tmp[i];
//////////////////// ///////////////////////
class MergeSortDemo
{ public static void main(String[] args)
{ int[] arr ={75, 40, 10, 90, 50, 95, 55, 15, 65};
MergeSort ms = new MergeSort(arr);
System.out.print("Sorted array:");
for( int i=0; i < arr.length; i++)
System.out.print(arr[i] + " ");


Time complexity of merger sort



Post a Comment

Note: only a member of this blog may post a comment.

Find Us On Facebook

Computer Basics


C Programming


Java Tutorial


Data Structures


MS Office


Database Management