Merge sorting c program

We will depict the pointer by underlining the corresponding element where the pointer points to. Left array: [ 1 , 4, 5, 6]. Right array: [ 2 , 3, 7]. As can be seen, the pointer of the left array is at 1 and the pointer of the right array is at 2. We pick the smaller one and put it in the final merged array and move the corresponding pointer. After doing this, we will have the following state:. Left array: [ 4 , 5, 6]. Here the pointers are now at 4 and 2 respectively.

We again do what we did above - pick the smaller one and put it in the final merged array and move the corresponding pointer. We will get the following:. Right array: [ 3 , 7]. Right array: [ 7 ]. Continuing this exercise, we can see that we are successfully able to get the final merged array in the sorted form:.

So, as can be seen, we started with an unsorted array and we were successfully able to get a sorted array. Another question that is to be answered - how were the left and the right arrays sorted? Well, we sorted them recursively using the same technique as above. For instance, consider the right array: [2, 7, 3]. To sort it, we will break it again into 2 sub-arrays: [2, 7] and [3].

Both these sub-arrays are already sorted so we can simply merge them by using the technique explained above to get the sorted array [2, 3, 7]. Take a look at the following image to understand how this same procedure is recursively applied on the subarrays:. Let us understand the detailed steps involved in performing a merge sort in the above array:. Observe one important point - we need a separate array in order to store the data of the final merged array.

This means that merge sort requires additional space. Here is an animation that explains the same. Before we get into the actual code, let us take a look at the pseudo code. So, we do nothing in this case and simply return.

We plan to partition the array into 2 sub-arrays of almost equal lengths. These subarrays are a[i.. Here, we are recursively sorting a[i.. Once we have these 2 sorted subarrays in place, the rest of the code simply merges the 2. Complexity gives a rough idea of the time taken to execute the algorithm as a function of the size of the input.

For instance, let T n be the time taken to perform merge sort on an array of size n. With some maths, this equation can be solved as. Here, T 1 and c are constants. Since the term nlog 2 n is larger than n, we can see that nlog 2 n is the dominant term. The complexity of bubble sort algorithm on the other hand as we saw was O n 2.

Merge sort is an interesting algorithm and forms a great case-study to understand data structures and algorithms. In order to develop strong foundations in computer science, you are advised to thoroughly understand various sorting algorithms that will help you pick up the basics.

Entrepreneur, Coder, Speed-cuber, Blogger, fan of Air crash investigation! Fascinated by the world of technology he went on to build his own start-up - AllinCall Research and Solutions to build the next generation of Artificial Intelligence, Machine Learning and Natural Language Processing based solutions to power businesses.

View all posts by the Author. By signing up, you agree to our Terms of Use and Privacy Policy. Forgot Password? This website or its third-party tools use cookies, which are necessary to its functioning and required to achieve the purposes illustrated in the cookie policy. By closing this banner, scrolling this page, clicking a link or continuing to browse otherwise, you agree to our Privacy Policy.

Popular Course in this category. School Performance Rankings. Toppers in Class Links to Infra Details of Various Schools. Popular Universities. Bangalore University. Calcutta University. Delhi University. Madras University. Mumbai University. Pune University. The DU Admission Mess. Brazen Unfairness of DU's cut-offs. School Performance Rankings Old. Top ISC Schools - ISC-Class 12 Toppers Moderation Mess. CBSE Score manipulation over a decade. Good CS Programs. How to pick a BTech branch or program.

CBSE K12 Toppers. That's me! Prashant Bhattacharji. Info for parents and students. Python for Data. Baby step with python for Data Science word count. Simple Regression with Matrix. Linear regression via Normal Equation. Predicting Flight Price with Tensorflow. Data Analysis with Pandas Basic. Linear Classification with Stochastic Gradient Descent. Ada-grad vs Bold-driver for linear classification.

R for Data. Data transformation in R using dplyr. String Manipulation in R. Text Preprocessing In R. What sets apart US univs? Common Core standards in Math. Facebook recommends Math. England: GCSE. GCE Performance. Popular articles. What kind of criteria should one use to pick a college? Gujarat School Fees Cap. Delhi Nursery Admissions: The mess. Examination Results ISC K12 Toppers. Fibonacci Numbers. Graphs of Cubic Polynomials. Basic Sorting and Searching Algorithms for Arrays, at a glance.

Merge sort is based on Divide and conquer method. It takes the list to be sorted and divide it in half to create two unsorted lists. The two unsorted lists are then sorted and merged to get a sorted list. The two unsorted lists are sorted by continually calling the merge-sort algorithm; we eventually get a list of size 1 which is already sorted. The two lists of size 1 are then merged. Divide the input which we have to sort into two parts in the middle.