Scribd
Upload
6 views4 pages

Merge Sort

The document contains a C program that implements the merge sort algorithm. It defines functions to merge two subarrays and to recursively sort an array using merge sort. The main function demonstrates the sorting of an example array and prints the sorted result.

Uploaded by

rahulchoudhary5938
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
6 views4 pages

Merge Sort

The document contains a C program that implements the merge sort algorithm. It defines functions to merge two subarrays and to recursively sort an array using merge sort. The main function demonstrates the sorting of an example array and prints the sorted result.

Uploaded by

rahulchoudhary5938
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

#include <stdio.

h>

#include <stdlib.h>

// Merges two subarrays of arr[].

// First subarray is arr[l..m]

// Second subarray is arr[m+1..r]

void merge(int arr[], int l, int m, int r){

int i, j, k;

int n1 = m - l + 1;

int n2 = r - m;

// Create temp arrays

int L[n1], R[n2];

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

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

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

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

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

// Merge the temp arrays back into arr[l..r

i = 0;

j = 0;

k = l;
while (i < n1 && j < n2) {

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

arr[k] = L[i];

i++;

else {

arr[k] = R[j];

j++;

k++;

// Copy the remaining elements of L[],

// if there are any

while (i < n1) {

arr[k] = L[i];

i++;

k++;

// Copy the remaining elements of R[],

// if there are any

while (j < n2) {

arr[k] = R[j];

j++;
k++;

// l is for left index and r is right index of the

// sub-array of arr to be sorted

void mergeSort(int arr[], int l, int r){

if (l < r) {

int m = l + (r - l) / 2;

// Sort first and second halves

mergeSort(arr, l, m);

mergeSort(arr, m + 1, r);

merge(arr, l, m, r);

// Driver code

int main(){

int arr[] = {38, 27, 43, 10};

int arr_size = sizeof(arr) / sizeof(arr[0]);


mergeSort(arr, 0, arr_size - 1);

int i;

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

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

printf("\n");

return 0;

You might also like