merge sort nr Algorithm
The merge sort algorithm is a highly efficient and widely used comparison-based sorting technique that works on the divide and conquer strategy. It is a recursive algorithm that continually splits the input list in half until it reaches the base case of either empty or single-element lists. The algorithm then merges the smaller sorted lists back together by comparing and arranging the elements in a sorted order, thus producing a final sorted array. The merge sort algorithm is well-regarded for its consistently strong performance, with a time complexity of O(n*log(n)) in the worst, average, and best-case scenarios.
The merge sort algorithm can be further optimized by implementing a non-recursive or iterative approach, referred to as the merge sort nr (non-recursive) algorithm. This approach eliminates the need for recursion by using loops to divide and merge the elements within the input list. The algorithm begins by treating each element as a single sorted list and repeatedly merging adjacent pairs of lists until only one sorted list remains. The merge sort nr algorithm maintains the same O(n*log(n)) time complexity as the recursive merge sort, but it reduces the space complexity and the risk of a stack overflow in systems with limited memory resources. Additionally, the iterative approach is more intuitive for some programmers to understand and implement, making it a valuable alternative to the traditional recursive merge sort.
/* 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
*/
