## Thursday, May 5, 2022

### Question 80 : Can you write algorithm for merge sort and also do you know complexity of merge sort?

`Merge sort` is divide and conquer sorting algorithm. It is efficient, comparison based sorting algorithm.

It works on below principle:

• `Divide` list into `sublist` of about half size in each iteration until each sublist has only one element.
• `Merge` each `sublist` repeatedly to create sorted list. It will run until we have only 1 sorted list. This will be the `sorted list`.

The below diagram will make it clearer:

Merge sort implementation

I have printed intermediate steps to understand the algorithm better

``````public class MergeSortMain {

static  int  arr[]={100,20,15,30,5,75,40};

public static void main(String args[])
{
// Print array before merge sort
System.out.println("Array before sorting:");
printArray(arr,0,arr.length-1);
System.out.println("-----------------------------");

mergeSort(0,arr.length-1);

System.out.println("-----------------------------");

// Print array after sorting
System.out.println("Array After sorting:");
printArray(arr,0,arr.length-1);

}

// Recursive algorithm for merge sort
public static void mergeSort(int start,int end)
{
int mid=(start+end)/2;
if(start<end)
{
// Sort left half
mergeSort(start,mid);
// Sort right half
mergeSort(mid+1,end);
// Merge left and right half
merge(start,mid,end);
}

}

private static void merge(int start, int mid, int end) {
// Initializing temp array and index
int[] tempArray=new int[arr.length];
int tempArrayIndex=start;

System.out.print("Before Merging:  ");
printArray(arr,start,end);

int startIndex=start;
int midIndex=mid+1;

// It will iterate until smaller list reaches to the end
while(startIndex<=mid && midIndex<=end)
{
if(arr[startIndex]< arr[midIndex])
{
tempArray[tempArrayIndex++]=arr[startIndex++];
}
else
{
tempArray[tempArrayIndex++]=arr[midIndex++];
}
}

// Copy remaining elements
while(startIndex<=mid)
{
tempArray[tempArrayIndex++]=arr[startIndex++];
}
while(midIndex<=end)
{
tempArray[tempArrayIndex++]=arr[midIndex++];
}

// Copy tempArray to actual array after sorting
for (int i = start; i <=end; i++) {
arr[i]=tempArray[i];
}

System.out.print("After merging:   ");
printArray(tempArray,start,end);
System.out.println();
}

public static void printArray(int arr[],int start,int end)
{
for (int i = start; i <=end; i++) {
System.out.print(arr[i]+" ");
}
System.out.println();
}
}``````
When you run above program , you will get following output:
Array before sorting:
100 20 15 30 5 75 40
—————————–
Before Merging: 100 20
After merging: 20 100
Before Merging: 15 30

After merging: 15 30

Before Merging: 20 100 15 30
After merging: 15 20 30 100

Before Merging: 5 75
After merging: 5 75

Before Merging: 5 75 40
After merging: 5 40 75

Before Merging: 15 20 30 100 5 40 75
After merging: 5 15 20 30 40 75 100

—————————–
Array After sorting:
5 15 20 30 40 75 100

## Time Complexity:

Best case: `O(nlogn)`
Average case: `O(nlogn)`
Worst case: `O(nlogn)`

Don't miss the next article!
Be the first to be notified when a new article or Kubernetes experiment is published.