mirror of https://github.com/TheAlgorithms/C
104 lines
2.3 KiB
C
104 lines
2.3 KiB
C
/* Program to demonstrate non recursive merge sort */
|
|
|
|
/* Merge sort is an effective sorting algorithm which falls under divide and
|
|
conquer paradigm and produces a stable sort. Merge sort repeatedly breaks down a
|
|
list into several sublists until each sublist consists of a single element and
|
|
merging those sublists in a manner that results into a sorted list.
|
|
|
|
Bottom-Up Merge Sort Implementation:
|
|
The Bottom-Up merge sort approach uses iterative methodology. It starts with the
|
|
“single-element” array, and combines two adjacent elements and also sorting the
|
|
two at the same time. The combined-sorted arrays are again combined and sorted
|
|
with each other until one single unit of sorted array is achieved. */
|
|
|
|
#include <stdio.h>
|
|
|
|
void mergesort(int x[], int n);
|
|
void show(int x[], int n);
|
|
|
|
void mergesort(int x[], int n)
|
|
{
|
|
int temp[50], i, j, k, lb1, lb2, ub1, ub2, size;
|
|
|
|
size = 1;
|
|
while (size < n)
|
|
{
|
|
lb1 = 0;
|
|
k = 0;
|
|
|
|
while (lb1 + size < n)
|
|
{
|
|
lb2 = lb1 + size;
|
|
ub1 = lb2 - 1;
|
|
if (ub1 + size < n)
|
|
ub2 = ub1 + size;
|
|
else
|
|
ub2 = n - 1;
|
|
|
|
i = lb1;
|
|
j = lb2;
|
|
|
|
while (i <= ub1 && j <= ub2)
|
|
if (x[i] < x[j])
|
|
temp[k++] = x[i++];
|
|
else
|
|
temp[k++] = x[j++];
|
|
|
|
while (i <= ub1) temp[k++] = x[i++];
|
|
|
|
while (j <= ub2) temp[k++] = x[j++];
|
|
|
|
lb1 = ub2 + 1;
|
|
}
|
|
|
|
for (i = 0; i <= ub2; i++) x[i] = temp[i];
|
|
|
|
size = size * 2;
|
|
|
|
show(x, n);
|
|
}
|
|
}
|
|
|
|
// function to show each pass
|
|
void show(int x[], int n)
|
|
{
|
|
int i;
|
|
for (i = 0; i < n; i++) printf("%d ", x[i]);
|
|
printf("\n\n");
|
|
}
|
|
|
|
int main() // main function
|
|
{
|
|
int i, n, x[20];
|
|
|
|
printf("Enter the number of elements: ");
|
|
scanf("%d", &n);
|
|
printf("Enter the elements:\n");
|
|
for (i = 0; i < n; i++) scanf("%d", &x[i]);
|
|
|
|
mergesort(x, n);
|
|
|
|
printf("Sorted array is as shown:\n");
|
|
for (i = 0; i < n; i++) printf("%d ", x[i]);
|
|
return 0;
|
|
}
|
|
|
|
/* Output of the Program*/
|
|
/*
|
|
Enter the number of elements: 5
|
|
Enter the elements:
|
|
15
|
|
14
|
|
13
|
|
12
|
|
11
|
|
14 15 12 13 11
|
|
|
|
12 13 14 15 11
|
|
|
|
11 12 13 14 15
|
|
|
|
Sorted array is as shown:
|
|
11 12 13 14 15
|
|
*/
|