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 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 »

Pattern 1 | Java

Problem Statement: Write a program to draw the following pattern of NxN(where N is the input): * * * * * * * * * * * * * * * * * * * * * * * * * (here, N=5) THE CODE Output: Here, the input is 8 Simplification : In the above problem, two for loops are used: 1. The first for loop is having i as counter variable with  initial value of 1 and ending value of 10 with an updation statement i++. 2. The second for loop is having j as counter variable with initial value of 1 and ending value of 10 with an updation statement j++. The second  for loop is used to print  * in the respective column (the value of j represents the column number). It is having a print statement System.out.println("* ") to print * in each column(for convenience, I've added a space for better visibility of columns in the output). The first for loop is used to define rows( the value of i represents the row number). It is having a print statement System.out.print() to change rows each time the second for ...
Discover More »

Kadane's Algorithm | The-Algorithm-Drive | MyCodingNetwork

Kadane's Algorithm Kadane’s algorithm is used to find largest contagious subarray sum for a given array. It is one of the most common types of algorithms used to find the subarray with largest sum. The time complexity of this algorithm is O(N) .     Output :            Code Explanation: On line 4, there’s an  int  array variable a[ ], which is the array on which we have to perform our task. We have stored the value of the array, in variable l. cur_max,  is a temporary variable for traversing the array and storing positive sum occurring and update it after each iteration.  global_max , is a variable for storing the highest sum of subarray. ‘ start ’ variable stores the starting index of the desired subarray and ‘ end ’ variable stores the last index of that subarray, that is, contagious subarray with the highest sum. Working: Talking about the working of this algorithm, it uses one for loop and the entire operation can be perfo...
Discover More »