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

Pattern 4 | Java | MyCodingNetwork | Alok Tripathi (Code 6)

Problem Statement: Write a program to draw the following pattern where number of rows are decided by the user and given to the program as input:         *       * *     * * *   * * * * * * * * * * * * * * * (Take a variable n which takes the number of rows as input from the user, For above example, n=6) OUTPUT: The above program is the extension of the previous program (Pattern #3). This program asks the user to input the number of rows that it wants in the program. For accepting the input, the program has Scanner class which has been extracted from the package java.util . In this program, we will learn how to receive data from the user. If you remember in three previous patterns, the program itself had the input of number of rows where n=8, but now the user will tell the program how many rows are to be added.   Simplification 1.     In Line 1, the java.util  package has been imported, to use the Scanner cl...
Discover More »

Pattern 6 | Java | MyCodingNetwork | Alok Tripathi (Code 8)

Problem Statement: Write a program to make a square and mark out its diagonals. Accept the length as input from the user and give output in the following manner: And ( In simple words, we have printed stars (*) on the boundary positions of the matrix and on the centre positions of the matrix we have printed blank space( ) )   THE CODE: Sample Output: In the above program, two int variables r to accept the length of square as input. On line 7, following statement is used to accept the input from the user: int r = sc . nextInt ();   For taking the input Scanner class has been used, more about Scanner class Algorithm: Two for loops are defined: ·         First for loop with counter variable i has initial value 1, conditional statement i less than or equal to r and an updating statement i++ . ·         Inside the first loop there is a second for loop, with counter variable j has ini...
Discover More »

Binary Search | The-Algorithm-Drive | MyCodingNetwork

Binary Search The next algorithm, we are going to study is Binary Search . As the name suggests, it is a searching algorithm. It is one of the very famous searching techniques. Unlike its counterpart linear search, it is way more advanced.  Time complexity of linear search is O(N) whereas that of binary search is O (log N). Source Code: Output Number Found at index =5 Working Let’s come on to the working of the algorithm, as you can see in the above program, we need a sorted array to perform binary search algorithm. 1.    Here, bin function in the above program it accepts 4 parameters, that is, the array arr , lower index low , higher index high and the searching number sn . 2.    Next, we have a do-while loop to check if high is greater than or equal to low (high>=low). If at any point of iteration this condition is not satisfied, it means the searching number sn does not exist in the array. Following is the algorithm for binary search: while ...
Discover More »