• Skip to main content
  • Skip to primary sidebar
  • Skip to secondary sidebar
  • Skip to footer

Computer Notes

Library
    • Computer Fundamental
    • Computer Memory
    • DBMS Tutorial
    • Operating System
    • Computer Networking
    • C Programming
    • C++ Programming
    • Java Programming
    • C# Programming
    • SQL Tutorial
    • Management Tutorial
    • Computer Graphics
    • Compiler Design
    • Style Sheet
    • JavaScript Tutorial
    • Html Tutorial
    • Wordpress Tutorial
    • Python Tutorial
    • PHP Tutorial
    • JSP Tutorial
    • AngularJS Tutorial
    • Data Structures
    • E Commerce Tutorial
    • Visual Basic
    • Structs2 Tutorial
    • Digital Electronics
    • Internet Terms
    • Servlet Tutorial
    • Software Engineering
    • Interviews Questions
    • Basic Terms
    • Troubleshooting
Menu

Header Right

Home » C » Merge Sort in C
Next →
← Prev

Merge Sort in C

By Dinesh Thakur

Merge Sort in C is a divide and conquer algorithm which John von Neumann developed in 1945. We divide the data into smaller pieces, recursively conquer each piece and merge the result into the final result until the original list is rebuild sorted. This tutorial will help you to understand Merge Sort In C in detail.

We’ll be covering the following topics in this tutorial:

  • What is Merge sort in C?
  • Merge Sort Methods
  • Divide & Conquer algorithm has 3 steps:
  • Time Complexity of Merge Sort in C
  • Merge Sort Algorithm
  • C Program For Merge Sort

What is Merge sort in C?

Merge sort uses divide and conquer to sort a particular array. In Merge sort, the original array is subdivided into a “nearly” equal-sized array. Then two sub-arrays are sorted separately. The two-sorted sub-arrays are then merged into a single sorted array through merging methods. Hence the name Merge Sort is given to this technique.

We keep splitting each of the sub-arrays till each sub-array contains just one item. A sub-array containing one item needs no sorting.

Merge sort is a comparison based stable algorithm. It requires less time to sort a partially sorted array. The complexity of the merge sort algorithm is O(n log n).

In-place, top-down, and bottom-up merge sort are different variants of merge sort.

Merge Sort Methods

Merge Sort is generally regarded as one of the best internal sorting methods. If the data is too large to be stored simultaneously in the memory, external sorting methods should be used. Small data blocks are loaded into the memory, sorted by an internal sorting method, and written out to a disc in external sorting methods. Sorted parts are then merged with merging algorithm variations.

Divide & Conquer algorithm has 3 steps:

1. Divide: Breaking the list into n sublists.
2. Conquer: Recursively splits the list.
3. Merge: Merges those sublists to produce a sorted list.

Merge sort is one of the most potent and quick sorting algorithms with the following time complexity

Time Complexity of Merge Sort in C

The complexity of the merge sort in every case is O (n log2 n). To understand we derive this time complexity for merge sort, two factors need to be considered.

(a) Number of recursive calls.
(b) Time is taken to merge each sub-array.

To understand the first factor, consider an array of n elements where n=2k where k>0. The initial call to MERGESORT () algorithm makes two recursive calls to it, dividing the array into two sub-arrays of n/2 elements. Moreover, each of the two recursive calls to MERGESORT() makes two further recursive calls to MERGESORT (), dividing the two sub-arrays into four sub-arrays of n/22 or n/4 elements each. This process continues, and the final recursive call (kth level) divides the sub-array into n sub-arrays of 1 (n/2k)element each. It takes k levels (log2n where n = 2k) of recursive calls to obtain n sub-arrays of one element. Thus complexity for the recursive call is O(log2n).
Now consider the other factor. The merge process makes at most (n – 1) comparisons among n elements in the two sub arrays. Each merge also requires n moves to a temporary array and n moves back to the original array. In total, each merge requires at most 3n – 1 operation, i.e. O(n).
Therefore, the overall complexity of the merge sort is O(n log2 n).

 

Note : An additional space of O(n) is required to merge two sorted arrays. Thus merge sort is not an in-place sorting algorithm.

Merge Sort Algorithm

MergeSort(arr[], left, right), Where left is the first indexed 
element & right is the last indexed element in the list. 
if right > left
1. Select the middle array index to break into two sublists : 
   middle = (left + right)/2
2. Call MergeSort for first sublist : 
   mergeSort(array, left, middle)
3. Call mergeSort for second sublist : 
   mergeSort(array, middle +1, right)
4. Recursively, merge two sublists in a sorted style, 
   leaving just one sorted array. : merge(array, left, middle, right)

Example:

1. Divide the unsorted list recursively until there is only one element remaining.

Merge Sort in C
2. Merge sublists recursively to produce sorted sublists until all the sublists merge and there is only one list left.

Merge Sort in C (Merge sublists)C Program For Merge Sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<stdio.h>
void mergesort(int a[],int l,int r);
void merge(int a[],int l1,int r1,int l2,int r2);
int main() {
 int a[30],n,l;
 printf("Enter number of elements:");
 scanf("%d",&n);
 printf("Enter array elements:");
 for(l=0;l<n;l++)
   scanf("%d",&a[l]);
   mergesort(a,0,n-1);
   printf("\nSorted array is :");
   for(l=0;l<n;l++)
     printf("%d ",a[l]);
     return 0;
}
void mergesort(int a[],int l,int r) {
 int mid;
 if(l<r) {
   mid=(l+r)/2;
   mergesort(a,l,mid); //left recursion
   mergesort(a,mid+1,r); //right recursion
   merge(a,l,mid,mid+1,r); //merging of two sorted sub-arrays
 }
}
void merge(int a[],int l1,int r1,int l2,int r2) {
 int temp[50]; //array used for merging
 int l,r,k;
 l=l1; //beginning of the first list
 r=l2; //beginning of the second list
 k=0;
 while(l<=r1 && r<=r2) //while elements in both lists {
   if(a[l]<a[r])
      temp[k++]=a[l++];
   else
      temp[k++]=a[r++];
}
 while(l<=r1) //copy remaining elements of the first list
   temp[k++]=a[l++];
   while(r<=r2) //copy remaining elements of the second list
     temp[k++]=a[r++];
     //Transfer elements from temp[] back to a[]
     for(l=l1,r=0;l<=r2;l++,r++)
       a[l]=temp[r];
}

C Program For Merge Sort

You’ll also like:

  1. C Program to Merge two Unsorted Arrays
  2. What is bubble sort in C with example?
  3. What is Insertion Sort in C with Example
  4. Selection Sort in C
  5. What is Bubble Sort
Next →
← Prev
Like/Subscribe us for latest updates     

About Dinesh Thakur
Dinesh ThakurDinesh Thakur holds an B.C.A, MCDBA, MCSD certifications. Dinesh authors the hugely popular Computer Notes blog. Where he writes how-to guides around Computer fundamental , computer software, Computer programming, and web apps.

Dinesh Thakur is a Freelance Writer who helps different clients from all over the globe. Dinesh has written over 500+ blogs, 30+ eBooks, and 10000+ Posts for all types of clients.


For any type of query or something that you think is missing, please feel free to Contact us.


Primary Sidebar

C Programming

C Programming Tutorials

  • C - History
  • C - Anatomy
  • C - Constants
  • C - Identifiers
  • C - Data Types
  • C - Libraries File
  • C - Header Files
  • C - Basic Language
  • C - Data Types Sizes
  • C - Header Files Importance
  • C - Escape Sequences
  • C - Main() Purpose
  • C - Program Procedure
  • C - Control Statements
  • C - Enumeration Constant
  • C - Add numbers
  • C - Return Statement
  • C - Avoid Goto
  • C - Command Line Arguments
  • C - Switch Case
  • C - Switch Case Limitations
  • C - getchar() and putchar()
  • C - Iteration Statements
  • C - Pass by Value and Reference
  • C - Structures and Unions
  • C - Structure
  • C - Dynamic Memory
  • C - Fgets and Fputs Functions
  • C - Gets() and Puts() Functions
  • C - Armstrong Number
  • C - Storage Classes
  • C - Fibonacci Series
  • C - Precision Setting
  • C - const Parameters

C - Variable & It's Type

  • C - Variables
  • C - Variable Lifetime
  • C - Static Variable
  • C - Register Variable
  • C - Global Variables
  • C - Auto Variables
  • C - Local Variables

C - Operator & Expressions

  • C - Operator
  • C - Boolean Operators
  • C - Bitwise Operator
  • C - Arithmetic Operators
  • C - Modulus Operator
  • C - Ternary Operator
  • C - Expressions
  • C - Arithmetic Expressions

C - Array

  • C - Arrays
  • C - Array Types
  • C - Array Characteristics
  • C - Static Arrays
  • C - Global Arrays
  • C - 3D Arrays
  • C - Dynamic Arrays
  • C - Pointer to 3D Arrays
  • C - Array Elements Hold
  • C - Arrays as Function Parameters
  • C - Accessing Matrix Elements
  • C - File Handling
  • C - Matrix Multiplication
  • C - Dynamic Memory Allocation

C - Searching & Sorting

  • C - Data Structures
  • C - Linear Search
  • C - Bubble Sort
  • C - Merge Sort
  • C - Linked List
  • C - Insertion Sort
  • C - Binary Search
  • C - Selection Sort
  • C - Quick Sort

C - Functions

  • C - Functions
  • C - Functions Advantages
  • C - Void Functions
  • C - Function Call
  • C - Default Return Value
  • C - String functions

C - Pointer

  • C - Pointers
  • C - Type Casting Of Pointers
  • C - Pointer Advantages
  • C - Pointers Initialization
  • C - Vectors and Pointers

C - Differences

  • C - C Vs C++
  • C - Formal Args. Vs Actual Args.
  • C - Keywords Vs Identifiers
  • C - Strings Vs Character Arrays
  • C - Address Vs Dereference Operator
  • C - Goto Vs longjmp
  • C - Declaring Vs Defining Variable
  • C - String Vs Array
  • C - Call by Value Vs Reference
  • C - Structure Vs Union
  • C - For Vs While loops
  • C - Compiler Vs Interpreter

C - Programs

  • C Program Standard Deviation
  • C Program Calculate Tax
  • C Program Sum Series
  • C Program Merge Arrays
  • C Program Euclid’s Algorithm
  • C Program Print Weekdays
  • C Program Sum of Digits
  • C Program Print a list
  • C Program Print Pythagorean
  • C Program Quiz program
  • C Program Display Table
  • C Program Print Comma-Separated
  • C Program Prints Prime Numbers
  • C Program for Print Integer
  • C Program Count Number
  • C Program Print Color Name
  • C Program Print Odd Numbers
  • C Program Calculate area
  • C Program for a Menu
  • C Program Add Two Vectors
  • C Program Array Addresses
  • C Program Division by Zero Error
  • C Program Compare two Dates
  • C Program Tower of Hanoi
  • C Program return 3 Numbers
  • C Program for Prime Numbers
  • C Program for Factorial
  • C Program for Palindrome

Other Links

  • C Programming - PDF Version

Footer

Basic Course

  • Computer Fundamental
  • Computer Networking
  • Operating System
  • Database System
  • Computer Graphics
  • Management System
  • Software Engineering
  • Digital Electronics
  • Electronic Commerce
  • Compiler Design
  • Troubleshooting

Programming

  • Java Programming
  • Structured Query (SQL)
  • C Programming
  • C++ Programming
  • Visual Basic
  • Data Structures
  • Struts 2
  • Java Servlet
  • C# Programming
  • Basic Terms
  • Interviews

World Wide Web

  • Internet
  • Java Script
  • HTML Language
  • Cascading Style Sheet
  • Java Server Pages
  • Wordpress
  • PHP
  • Python Tutorial
  • AngularJS
  • Troubleshooting

 About Us |  Contact Us |  FAQ

Dinesh Thakur is a Technology Columinist and founder of Computer Notes.

Copyright © 2025. All Rights Reserved.

APPLY FOR ONLINE JOB IN BIGGEST CRYPTO COMPANIES
APPLY NOW