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

Labels:

Popular posts from this blog

Exploring Uninformed Search in Artificial Intelligence: Basics and Applications

  In artificial intelligence (AI), search algorithms are essential for solving a variety of problems, from navigating a maze to scheduling tasks. Uninformed search, also known as blind search, is a fundamental category of search techniques where the algorithm has no additional information about the states beyond what is provided in the problem definition to guide the search. This page delves into the basics of uninformed search algorithms, their types, and their applications in AI. Understanding Uninformed Search Uninformed search algorithms explore the search space without any guidance on which paths might lead to the goal more efficiently. They rely solely on the information available from the initial problem setup, such as the start state, goal state, and possible actions. This approach contrasts with informed search algorithms, which utilize heuristics to make more educated guesses about the best path to take. Types of Uninformed Search Algorithms   Several uninformed se...
Discover More »

Artificial Intelligence Playlist

Here's a playlist specifically dedicated to Artificial Intelligence. Make sure to follow it, as a whole lot of new AI videos coming up... 1. Concept of State in AI 2. Uninformed Search in AI 3. Breadth First Search | Part 1 4. Breadth First Seach | Part 2 | Algorithm & Working and many more to come...
Discover More »

Bubble Sort | Java & Python | MyCodingNetwork | Alok Tripathi

  Bubble Sort is a simple sorting algorithm that works by repeatedly comparing and swapping adjacent elements in an array until they are in the correct order. It is called bubble sort because the smaller elements "bubble" to the top of the array, while the larger elements sink to the bottom. Quick Video Explanation: How Bubble Sort Works Bubble sort works by iterating through the array from left to right and comparing each pair of adjacent elements. If the element on the left is larger than the element on the right, they are swapped. This way, the largest element in the array moves to the rightmost position in each iteration. This process is repeated until no more swaps are needed, which means the array is sorted. To illustrate how bubble sort works, let's use the example of sorting the array [30,90,50,10,40] in ascending order. First Iteration/Pass: The first step is to compare the first two elements, 30 and 90. Since 30 is smaller than 90, they are already i...
Discover More »