# Merge Sort in C

## How Merge Sort Works in C

Merge Sort is an example of the divide and conquer approach. It divides the array into equal halves and then combines in a sorted manner. In merge sort the unsorted list is divided into N sub-lists, each having one element.

 Time Complexity Θ(n Log n) Best Case Ω(n Log n) Worst Case O(n Log n) Space Complexity O(n)

## Execution of Merge sort Program in C

#### Dividing

For an unsorted array and we will make a sorted array by using the merge sort algorithm in this array will be used divide and conquer technique.

First of all the array will be divided into N sub-arrays that is the array divided until each has only one element.

#### Conquering/Merging

The N sub-Arrays will then be merged one by one. Make sure that at each merging step the subarray becomes sorted (see image below). This part of the algorithm is called a conquering/merging.

The sub-arrays are merged in sorted fashion one by one till the resultant is the size of the actual array.

## Program for Merge Sort

• Method 1 – Two temporary subarrays
• Method 2 – One Temporary subarray

Both will have the space complexity of O(N) as the combined size of two temporary arrays in method 1 will be the same as single temporary array used in method 2.

### Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

## Quick Facts about Merge Sort

• The complexity of the merge sort algorithm is O(NlogN) where N is the number of elements to sort.
• It can be applied  to file of any sizes.
• In Merge sort all the elements are divided into two sub-array again and again until one element is left.
• After the completion of the divide and conquer the elements are merged to make a sorted array .
• This sorting is less efficient and it require more space as compare to other sorting,

• Fast ! Time complexity : O(N Log N)
• Reliable, it gives same time complexity in all cases.
• Tim sort variant of this really powerful (Not important for Placements)

• Space Complexity sucks !!!
• Space Complexity : O(n), most other algorithm have O(1)

### Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Question 1.Prakash is using Merge sort to sort an array consisting of 2048 elements. After how many passes the array will be completely
sorted?

1. 10
2. 11
3. 9
4. 12

(Cisco, Goldman)

no. of stages = ciel(log2(2048)) = 11

The number of iterations to do so will always be ciel(log2(number of elements))

## Sorting

Sorting algorithms are easy to learn but are really important for college semester exams and companies offering package between 3 – 6 LPA would ask direct searching questions in online test/ interviews.