[go: up one dir, main page]
Scribd
Upload
32 views5 pages

Exp 8 - NLL

The document describes the merge sort algorithm. It explains that merge sort divides an array into halves, recursively sorts the halves, and then merges the sorted halves into a single sorted array. The key steps are dividing, conquering by recursively sorting sub-problems, and merging. Merge sort has a time complexity of O(n log n) in average and worst cases but requires O(n) additional space for a temporary array. Pseudocode and C code are provided to implement merge sort.

Uploaded by

jay
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
32 views5 pages

Exp 8 - NLL

The document describes the merge sort algorithm. It explains that merge sort divides an array into halves, recursively sorts the halves, and then merges the sorted halves into a single sorted array. The key steps are dividing, conquering by recursively sorting sub-problems, and merging. Merge sort has a time complexity of O(n log n) in average and worst cases but requires O(n) additional space for a temporary array. Pseudocode and C code are provided to implement merge sort.

Uploaded by

jay
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 5

RCPIT, Shirpur Department of Electronics and Telecommunication

Name of Student:

Expt No: 08 Roll No: Batch:

Title of Experiment: WAP to implement merge sort

Date of Performance: Date of Submission:

Marks: Sign:

AIM: Implementation of merge sort.


THEORY:
Merge sort is based on the divide-and-conquer paradigm. Divide means partitioning the n-element
array to be sorted into two sub-arrays of n/2 elements. If A is an array containing zero or one element,
then it is already sorted. However, if there are more elements in the array, divide A into two sub-
arrays, A1 and A2, each containing about half of the elements of A.

Conquer means sorting the two sub-arrays recursively using merge sort.

Combine means merging the two sorted sub-arrays of size n/2 to produce the sorted array of n
elements.

Merge sort algorithm focuses on two main concepts to improve its performance (running time):

● A smaller list takes fewer steps and thus less time to sort than a large list.
● As number of steps is relatively less, thus less time is needed to create a sorted list from two
sorted lists rather than creating it using two unsorted lists.

The basic steps of a merge sort algorithm are as follows:

● If the array is of length 0 or 1, then it is already sorted.


● Otherwise, divide the unsorted array into two sub-arrays of about half the size.
● Use merge sort algorithm recursively to sort each sub-array.
● Merge the two sub-arrays to form a single sorted list.

The merge sort algorithm uses a function Merge which combines the sub-arrays to form a sorted
array. While the merge sort algorithm recursively divides the list into smaller lists, the merge
algorithm conquers the list to sort the elements in individual lists. Finally, the smaller lists are merged
to form one list.

Its worst-case running time has a lower order of growth than insertion sort.

Data Structure & Algorithms Laboratory Page No.


RCPIT, Shirpur Department of Electronics and Telecommunication

To understand the merge algorithm, consider the figure below which shows how we merge two lists
to form one list. For ease of understanding, we have taken two sub-lists each containing four elements.
The same concept can be utilized to merge four sub-lists containing two elements, or eight sub-lists
having one element each.

Compare ARR[I] and ARR[J], the smaller of the two is placed in TEMP at the location specified by
INDEX and subsequently the value I or J is incremented.

When I is greater than MID, copy the remaining elements of the right sub-array in TEMP.

Algorithm for Merge Sort

MERGE_SORT (ARR, BEG, END)


Step 1: IF BEG < END
SET MID = (BEG + END)/2
CALL MERGE_SORT (ARR, BEG, MID)
CALL MERGE_SORT (ARR, MID + 1, END)
MERGE (ARR, BEG, MID, END)
[END OF IF]
Step 2: END
Data Structure & Algorithms Laboratory Page No.
RCPIT, Shirpur Department of Electronics and Telecommunication

Algorithm for Merge:

MERGE (ARR, BEG, MID, END)


Step 1: [INITIALIZE] SET I = BEG, J = MID + 1, INDEX = 0
Step 2: Repeat while (I <= MID) AND (J<=END)
IF ARR[I] < ARR[J]
SET TEMP[INDEX] = ARR[I]
SET I = I + 1
ELSE
SET TEMP[INDEX] = ARR[J]
SET J = J + 1
[END OF IF]
SET INDEX = INDEX + 1
[END OF LOOP]
Step 3: [Copy the remaining elements of right sub‐array, if any]
IF I > MID
Repeat while J <= END
SET TEMP[INDEX] = ARR[J]
SET INDEX = INDEX + 1, SET J = J + 1
[END OF LOOP]
[Copy the remaining elements of left sub‐array, if any]
ELSE
Repeat while I <= MID
SET TEMP[INDEX] = ARR[I]
SET INDEX = INDEX + 1, SET I = I + 1
[END OF LOOP]
[END OF IF]
Step 4: [Copy the contents of TEMP back to ARR] SET K=
Step 5: Repeat while K < INDEX
SET ARR[K] = TEMP[K]
SET K = K + 1
[END OF LOOP]
Step 6: END

The running time of merge sort in the average case and the worst case can be given as O(n log n).
Although merge sort has an optimal time complexity, it needs an additional space of O(n) for the
temporary array TEMP.

Data Structure & Algorithms Laboratory Page No.


RCPIT, Shirpur Department of Electronics and Telecommunication

CODE:
#include <stdio.h>
#include <conio.h>
#define size 100

void merge(int a[], int, int, int);


void merge_sort(int a[],int, int);

void main()
{
int arr[size], i, n;
printf("\n Enter the number of elements in the array : ");
scanf("%d", &n);
printf("\n Enter the elements of the array: ");
for(i= 0;i < n; i++)
{
scanf("%d", &arr[i]);
}
merge_sort(arr, 0, n-1);
printf("\n The sorted array is: \n");
for(i = 0; i < n; i++)
printf(" %d\t", arr[i]);
getch();
}

void merge(int arr[], int beg, int mid, int end)


{
int i = beg, j = mid + 1, index = beg, temp[size], k;
while((i<=mid) && (j<=end))
{
if(arr[i] < arr[j])
{
temp[index] = arr[i];
i++;
}
else
{
temp[index] = arr[j];
j++;
}
index++;
}
if(i>mid)
{
while(j<=end)
{
Data Structure & Algorithms Laboratory Page No.
RCPIT, Shirpur Department of Electronics and Telecommunication
temp[index] = arr[j];
j++;
index++;
}
}
else
{
while(i<=mid)
{
temp[index] = arr[i];
i++;
index++;
}
}

for(k=beg;k<index;k++)
arr[k] = temp[k];
}

void merge_sort(int arr[], int beg, int end)


{
int mid;
if(beg<end)
{
mid = (beg+end)/2;
merge_sort(arr, beg, mid);
merge_sort(arr, mid+1, end);
merge(arr, beg, mid, end);
}
}

CONCLUSION:

________________________________________________________________________________

________________________________________________________________________________

________________________________________________________________________________

________________________________________________________________________________

________________________________________________________________________________

Data Structure & Algorithms Laboratory Page No.

You might also like