Skip to main content

Merge Sort | Algorithm | MyCodingNetwork

Merge Sort

Hi there, I am back with another article on one of the most important algorithms in the world of DSA. In this article we would be covering Merge Sort and talk about its various aspects. So, without wasting much time let's jump into the topic right away.

Merge sort is another type of sorting algorithm whose time complexity is O(N*logN). The worst, average and best time complexity of merge sort always remains same, that is, O(N*logN). You must be thinking why the time complexity is same for all cases. Well, the answer to that we will get as we move further in our discussion.

It works on divide and conquer technique, where the given array is divided into smaller somebodies of two halves and then sorting is done.

Source Code:

conquer() function:


divide( ) function:



main( ) function:



Output:

#1 

In the above example, user first enters the length of the array, and then the array elements. The highlighted part are the elements of array after sorting.

#2
Let's take another example.

How it works:


Working:

In the source code, it first takes the array length and its element as input from the user and then divide( ) function is called/invoked on line 73. As shown above, inside the divide( ) function the array is being continuously divided recursively into two halves.

After this, conquer( ) function is used to sort the given sub-arrays. This process takes place inside the function by creating L[ ] and R[ ] integer arrays where the elements of first half is stored in L[ ] array and similarly for second-half R[ ] array is used. 

In further steps, the elements of both the arrays are compared as shown on line 22(L[i]<=R[j]) of the code and the elements are then placed inside the bigger array A[ ](out of which the two subparts are being extracted) according to the requirement, that is, either ascending or descending order.


Why Best, Average and Worst Time Complexity same?

Did you get the answer? If not, then try to understand the methodology of this code. 

See, neither the divide function nor the conquer function depends on the order of elements. The divide function will keep on dividing the array even if the array is sorted. Similarly, the conquer function would traverse and check each element within the given range irrespective of the order in which the elements are arranged (sorted or unsorted).


Hope you liked this explanation, for any doubt/feedback/improvements/corrections you can comment down in the comment section.
Labels:

Popular posts from this blog

Print a Linked List in Reverse Order | Linked List | Java | MyCodingNetwork

  Print a Linked List in Reverse Order After mastering the four standard operations on a Linked List - Creation, Traversal, Insertion, and Deletion - we will now proceed to the next topic: ' Printing a Linked List in Reverse Order '. It serves as a continuation of our previous discussions. We will build upon the topics and ideas that we have previously explored to further our understanding about Linked List. We 'll be using recursive approach for the implementation. For this a separate recursive function would be needed. Concept of stack is also implemented for print statement. Let's discuss the algorithm for the same: Algorithm: Create a function printReverse() , which takes 'head ' of the Linked List as the parameter. Take a temporary node ' cur ' and assign it with the head of the list. Create a base case which checks if cur==null . If base case is TRUE, then function would return . If base case is FALSE, then the statements following that base case ...
Discover More »

Pattern 2 | Java

  Problem Statement: Write a program to draw the following pattern: * * * * * * * * * * * * * * * (take a variable n which decides the number of rows, for above example, n=5) THE CODE Output: *  * *  * * *  * * * *  * * * * *  * * * * * *          * * * * * * *        * * * * * * * *      * * * * * * * * *    * * * * * * * * * * Simplification : In the above problem, the value of n is 10 (i.e., the number of rows are 10) 1. In the first for loop we have i as the counter variable with initial value of 1 and having a condition i.e. i should be less than or equal to n.  It has a print statement after the second for loop,  System.out.println(); w hich is used for changing the row, each time for the second for loop terminates. 2. In the second for loop we have j as the counter variable with initial value of 1 having a condition i.e. j  should be  less than or equal to i (t...
Discover More »

Code #1 | Hello Java | Basics of Java

Today starting with a very basic coding program in Java. So, the program is Write a program in Java to print "Hello Java!" Output: Hello Java!
Discover More »