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.                            

 

 Share This

You may also like

Kubernetes Microservices
Python AI/ML
Spring Framework Spring Boot
Core Java Java Coding Question
Maven AWS