C Program to implement Merge Sort using Iterative Approach - BunksAllowed

BunksAllowed is an effort to facilitate Self Learning process through the provision of quality tutorials.

Community

demo-image

C Program to implement Merge Sort using Iterative Approach

Share This
Source Code
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<stdio.h>
#include<stdlib.h>
int main() {
int *arr, *temp, i, j, k, n, size, l1, h1, l2, h2;
/*l1=lower index of one subarray;
l2=lower index of another subarray;
h1=higher index of one subarray;
h2=higher index of another subarray;*/
printf("Enter the number of elements : ");
scanf("%d", &n);
arr = (int*) malloc(sizeof(int) * n);
temp = (int*) malloc(sizeof(int) * n);
printf("\nenter the elements:");
for (i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
/*l1 lower bound of first pair and so on*/
for (size = 1; size < n; size = size * 2) {
l1 = 0;
k = 0; /*Index for temp array*/
while (l1 + size < n) {
h1 = l1 + size - 1;
l2 = h1 + 1;
h2 = l2 + size - 1;
/* h2 exceeds the limlt of arr */
if (h2 >= n)
h2 = n - 1;
/*Merge the two pairs with lower limits l1 and l2*/
i = l1;
j = l2;
while (i <= h1 && j <= h2) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
while (i <= h1)
temp[k++] = arr[i++];
while (j <= h2)
temp[k++] = arr[j++];
/**Merging completed**/
/*Take the next two pairs for merging */
l1 = h2 + 1;
}
/*any pair left */
for (i = l1; k < n; i++)
temp[k++] = arr[i];
for (i = 0; i < n; i++)
arr[i] = temp[i];
}
printf("Sorted list is :\n");
for (i = 0; i < n; i++)
printf("%d|", arr[i]);
return 0;
}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Happy Exploring!

Comment Using!!

No comments:

Post a Comment

Note: Only a member of this blog may post a comment.