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

AOAEXP03

The document presents a C program that implements the Merge Sort algorithm, which sorts an array of integers. It includes functions for merging subarrays and printing the array after each pass of sorting. The program dynamically allocates memory for the array and handles user input for the number of elements and their values.

Uploaded by

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

AOAEXP03

The document presents a C program that implements the Merge Sort algorithm, which sorts an array of integers. It includes functions for merging subarrays and printing the array after each pass of sorting. The program dynamically allocates memory for the array and handles user input for the number of elements and their values.

Uploaded by

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

EXPERIMENT: 03

//Parth More_SE_B_32

//Merge Sort Algorithm

#include <stdio.h>

#include <stdlib.h> // Required for malloc()

int passCount = 1; // Global variable to track sorting passes

// Function to print the array with "Pass X" format

void printArray(int arr[], int size) {

int i;

printf("Pass %d: ", passCount++);

for (i = 0; i < size; i++) {

printf("%d ", arr[i]);

printf("\n");

// Function to merge two subarrays

void merge(int arr[], int left, int mid, int right) {

int i, j, k;

int n1, n2;

int *L, *R; // Use pointers for dynamic allocation

n1 = mid - left + 1; // Size of left subarray

n2 = right - mid; // Size of right subarray

// Allocate memory dynamically

L = (int *)malloc(n1 * sizeof(int));

R = (int *)malloc(n2 * sizeof(int));

if (L == NULL || R == NULL) {

printf("Memory allocation failed!\n");

exit(1);
}

// Copy data to temporary arrays L[] and R[]

for (i = 0; i < n1; i++)

L[i] = arr[left + i];

for (j = 0; j < n2; j++)

R[j] = arr[mid + 1 + j];

// Merge the temporary arrays back into arr[left..right]

i = 0; // Initial index of left subarray

j = 0; // Initial index of right subarray

k = left; // Initial index of merged subarray

while (i < n1 && j < n2) {

if (L[i] <= R[j]) {

arr[k] = L[i];

i++;

} else {

arr[k] = R[j];

j++;

k++;

// Copy remaining elements of L[] if any

while (i < n1) {

arr[k] = L[i];

i++;

k++;

// Copy remaining elements of R[] if any

while (j < n2) {


arr[k] = R[j];

j++;

k++;

// Display the array after merging

printArray(arr, right + 1);

// Free allocated memory

free(L);

free(R);

// Merge Sort function (Recursive)

void mergeSort(int arr[], int left, int right) {

int mid;

if (left < right) {

mid = left + (right - left) / 2; // Find the middle point

// Sort first and second halves

mergeSort(arr, left, mid);

mergeSort(arr, mid + 1, right);

// Merge the sorted halves

merge(arr, left, mid, right);

// Main function

int main() {

int n, i;

int *arr; // Use dynamic allocation

// Get the number of elements

printf("Enter the number of elements: ");


scanf("%d", &n);

// Allocate memory dynamically

arr = (int *)malloc(n * sizeof(int));

if (arr == NULL) {

printf("Memory allocation failed!\n");

return 1;

// Get the elements from the user

printf("Enter %d elements:\n", n);

for (i = 0; i < n; i++) {

scanf("%d", &arr[i]);

// Show original array

printf("\nOriginal array: ");

for (i = 0; i < n; i++) {

printf("%d ", arr[i]);

printf("\n");

// Call Merge Sort

printf("\nSorting Process:\n");

mergeSort(arr, 0, n - 1);

// Show sorted array

printf("\nSorted array: ");

for (i = 0; i < n; i++) {

printf("%d ", arr[i]);

printf("\n");
// Free allocated memory

free(arr);

return 0;

You might also like