Merge Sort Program in C with Example - Sanfoundry (original) (raw)

Problem Description

Write a C program to perform a merge sort using recursion and function.

What is Merge Sort?

Merge Sort is a divide and conquer-based sorting algorithm. In this sorting algorithm the unsorted array keeps on dividing into two halves until the array is either empty or contains only one element, which is the base case of Merge Sort, and then the halves are combined/Merged in sorted order producing a sorted array. It is one of the most popular and efficient sorting techniques.

Problem Solution

Example:

If the input array is {7, 2, 3, 10, 1, 0, 6, 9}

the expected output array will have data as {0, 1, 2, 3, 6, 7, 9, 10}

Complete Approach of Merge Sort:

Consider an unsorted array as shown in the figure.

advertisement

Merge Sort Algorithm

Start

1. Declare Array, left, right and mid variables
2. Find mid by formula mid = (left+right)/2
3. Call MergeSort for the left to mid
4. Call MergeSort for mid+1 to right
5. Continue step 2, 3, and 4 while the left is less than the right
6. Then Call the Merge function End

There are several ways to write an merge sort program in C language. Let’s discuss all the ways in detail.

• Merge Sort Program in C using Recursion and Function
• Merge Sort Program in C using Linked List

Method 1: (Using Recursion and Function)

In this method, we use recursion and function to sort an array of numbers using the merge sort algorithm.

Program/Source Code

Here is the source code of the C program to sort an array of integers using Merge Sort Algorithm. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

1. /*
2. • C Program to Perform Merge Sort using Recursion and Functions
3. */
4. #include <stdio.h>
5. #include <stdlib.h>
6. // merge function
7. void Merge(int arr[], int left, int mid, int right)
8. {
9. int i, j, k;
10. int size1 = mid - left + 1;
11. int size2 = right - mid;
12. // created temporary array
13. int Left[size1], Right[size2];
14. // copying the data from arr to temporary array
15. for (i = 0; i < size1; i++)
16. Left[i] = arr[left + i];
17. for (j = 0; j < size2; j++)
18. Right[j] = arr[mid + 1 + j];
19. // merging of the array
20. i = 0; // intital index of first subarray
21. j = 0; // inital index of second subarray
22. k = left; // initial index of parent array
23. while (i < size1 && j < size2)
24. {
25. if (Left[i] <= Right[j])
26. {
27. arr[k] = Left[i];
28. i++;
29. }
30. else
31. {
32. arr[k] = Right[j];
33. j++;
34. }
35. k++;
36. }
37. // copying the elements from Left[], if any
38. while (i < size1)
39. {
40. arr[k] = Left[i];
41. i++;
42. k++;
43. }
44. // copying the elements from Right[], if any
45. while (j < size2)
46. {
47. arr[k] = Right[j];
48. j++;
49. k++;
50. }
51. }
52. //merge sort function
53. void Merge_Sort(int arr[], int left, int right)
54. {
55. if (left < right)
56. {
57. int mid = left + (right - left) / 2;
58. // recursive calling of merge_sort
59. Merge_Sort(arr, left, mid);
60. Merge_Sort(arr, mid + 1, right);
61. Merge(arr, left, mid, right);
62. }
63. }
64. // driver code
65. int main()
66. {
67. int size;
68. printf("Enter the size: ");
69. scanf("%d", &size);
70. int arr[size];
71. printf("Enter the elements of array: ");
72. for (int i = 0; i < size; i++)
73. {
74. scanf("%d", &arr[i]);
75. }
76. Merge_Sort(arr, 0, size - 1);
77. printf("The sorted array is: ");
78. for (int i = 0; i < size; i++)
79. {
80. printf("%d ", arr[i]);
81. }
82. printf("\n");
83. return 0;
84. }

Program Explanation

1. The MergeSort function takes the value of the minimum and maximum index of the array
2. It calculates the mid by the formula (low+high)/2 and recursively calls itself for low to mid and mid+1 to high and then calls the merge function to merge the sorted array.
3. The Merge function merges the two arrays by comparing the value in each and taking the minimum value in the newly created auxiliary array.
4. At last, whichever array is non-empty its value is just copied in the auxiliary array.
5. In the Driver Program user just declare the array and takes the input and calls the Merge Sort and merge function as shown in the code and prints the sorted result using for loop.

Time Complexity: O(nlogn)
Time Complexity of Merge Sort is O(nlogn) for best, average, and worst case.

Space Complexity: O(n)
Space Complexity of Merge Sort using an array is O(n), because Merge Sort requires an Auxiliary/temporary array for copying the elements.

Runtime Test Cases

Here’s the run time test cases for Merge sort algorithm for 3 different input cases.

Test Case 1 – Average Case: Here, the elements are entered in random order.

/* Average case */ Enter the size: 8 Enter the elements of array: 7 2 3 10 1 0 6 9 The sorted array is: 0 1 2 3 6 7 9 10

Test Case 2 – Best Case: Here, the elements are already sorted.

/* Best case */   Enter the size: 5 Enter the elements of array: -7 -3 8 9 12 The sorted array is: -7 -3 8 9 12

Test Case 3 – Worst Case: Here, the elements are reverse sorted.

/* Worst case */   Enter the size: 4 Enter the elements of array: 84 32 3 -9 The sorted array is: -9 3 32 84

Method 2: (Using Linked List)

In this method, an integer linked list is sorted using the merge sort technique.

A linked list cannot be accessed randomly and because of this slow access time, sorting algorithms like quick sort cannot be applied to it. So we use merge sort for this purpose. It works on divide and conquer technique.

Program/Source Code

Here is the source code of the C program to sort integers using Merge Sort on linked list technique. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

1. #include<stdio.h>
2. #include<stdlib.h>
3. struct node
4. {
5. int data;
6. struct node* next;
7. };
8. struct node* sortedmerge(struct node* a, struct node* b);
9. void frontbacksplit(struct node* source, struct node** frontRef, struct node** backRef);
10. void mergesort(struct node** headRef)
11. {
12. struct node* head = *headRef;
13. struct node* a;
14. struct node* b;
15. if ((head == NULL) || (head -> next == NULL))
16. {
17. return;
18. }
19. frontbacksplit(head, &a, &b);
20. mergesort(&a);
21. mergesort(&b);
22. *headRef = sortedmerge(a, b);
23. }
24. struct node* sortedmerge(struct node* a, struct node* b)
25. {
26. struct node* result = NULL;
27. if (a == NULL)
28. return(b);
29. else if (b == NULL)
30. return(a);
31. if ( a-> data <= b -> data)
32. {
33. result = a;
34. result -> next = sortedmerge(a -> next, b);
35. }
36. else
37. {
38. result = b;
39. result -> next = sortedmerge(a, b -> next);
40. }
41. return(result);
42. }
43. void frontbacksplit(struct node* source, struct node** frontRef, struct node** backRef)
44. {
45. struct node* fast;
46. struct node* slow;
47. if (source==NULL || source->next==NULL)
48. {
49. *frontRef = source;
50. *backRef = NULL;
51. }
52. else
53. {
54. slow = source;
55. fast = source -> next;
56. while (fast != NULL)
57. {
58. fast = fast -> next;
59. if (fast != NULL)
60. {
61. slow = slow -> next;
62. fast = fast -> next;
63. }
64. }
65. *frontRef = source;
66. *backRef = slow -> next;
67. slow -> next = NULL;
68. }
69. }
70. void printlist(struct node *node)
71. {
72. while(node != NULL)
73. {
74. printf("%d ", node -> data);
75. node = node -> next;
76. }
77. }
78. void push(struct node** head_ref, int new_data)
79. {
80. struct node* new_node = (struct node*) malloc(sizeof(struct node));
81. new_node -> data = new_data;
82. new_node->next = (*head_ref);
83. (*head_ref) = new_node;
84. }
85. int main()
86. {
87. struct node* a = NULL;
88. push(&a, 15);
89. push(&a, 10);
90. push(&a, 5);
91. push(&a, 20);
92. push(&a, 3);
93. push(&a, 26775);
94. mergesort(&a);
95. printf("\n Sorted Linked List is: \n");
96. printlist(a);
97. return 0;
98. }

Program Explanation

1. Return if head is NULL or the Linked List has only one element in the list
2. Divide the linked list into two halves.
frontbacksplit(head, &a, &b); (a and b are two halves)
3. Sort the two halves using mergesort(&a); and mergesort(&b);
4. SortedMerge() should be used to combine the sorted a and b, and headRef should be used to update the head reference. i.e. *headRef = sortedmerge(a, b);
5. Functions are used to print and insert the nodes in the linked list.

Time Complexity: O(nlogn)
Time Complexity of Merge Sort is O(nlogn) for best, average, and worst case.

Space Complexity: O(1)
Space Complexity of Merge Sort using Linked List is O(1), as it does not uses any auxiliary space with Linked List.

Runtime Test Cases

Sorted Linked List is: 3 5 10 15 20 26775

Conclusion:

• Merge Sort is a Stable Sorting Algorithm, that is it maintains the relative order for equal values/elements.
• Typically Merge Sort is not considered an in-place sorting algorithm.
• Merge Sort is used in External Sorting.
• External Sorting is the class of sorting algorithms that can handle a massive amount of data. It is required when data does not fit in the main memory and need to be stored in secondary memory.

Drawbacks:

• For Small datasets merge sort is slower than other algorithms such as selection or insertion sort.
• It requires additional space of O(n).
• Even if the array is sorted Merge Sort will run completely.

To practice programs on every topic in C, please visit “Programming Examples in C”, “Data Structures in C” and “Algorithms in C”.