Scribd
Upload
17 views

Merge Sort Algorithm

Uploaded by

23cs037
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
17 views

Merge Sort Algorithm

Uploaded by

23cs037
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/ 4

Merge Sort Algorithm

Description
Merge Sort is a divide-and-conquer sorting algorithm that splits the array into smaller
subarrays, sorts them, and merges them back into a sorted array.

Steps of the Algorithm


1. Divide: Recursively divide the array into two halves until each subarray has one element
or is empty.
2. Conquer: Merge the subarrays by comparing elements and sorting them during the merge
step.
3. Combine: Repeat the merging process until the entire array is sorted.

Algorithm
MERGE_SORT(arr, left, right)
1. If left < right:
2. Find mid = (left + right) / 2
3. Call MERGE_SORT(arr, left, mid)
4. Call MERGE_SORT(arr, mid + 1, right)
5. Call MERGE(arr, left, mid, right)

MERGE(arr, left, mid, right)


1. Create two temporary arrays:
LeftArray[] of size mid - left + 1
RightArray[] of size right - mid
2. Copy data from arr[left...mid] into LeftArray[] and from arr[mid + 1...right] into
RightArray[]
3. Initialize pointers i = 0 (LeftArray), j = 0 (RightArray), and k = left (original array)
4. While i < size of LeftArray and j < size of RightArray:
a. If LeftArray[i] <= RightArray[j]:
arr[k] = LeftArray[i]
i=i+1
b. Else:
arr[k] = RightArray[j]
j=j+1
c. Increment k = k + 1
5. Copy remaining elements of LeftArray[] (if any) to arr[]
6. Copy remaining elements of RightArray[] (if any) to arr[]

Example
Input: arr = [38, 27, 43, 3, 9, 82, 10]
Steps:
1. Divide the array until subarrays have one element:
- [38, 27, 43, 3, 9, 82, 10]
- Split into [38, 27, 43, 3] and [9, 82, 10]
- Further split: [38, 27], [43, 3], [9, 82], [10]

2. Merge step (sorting during merging):


- [38, 27] → [27, 38]
- [43, 3] → [3, 43]
- [9, 82] → [9, 82]

3. Combine sorted subarrays:


- [27, 38] and [3, 43] → [3, 27, 38, 43]
- [9, 82] and [10] → [9, 10, 82]

4. Final merge:
- [3, 27, 38, 43] and [9, 10, 82] → [3, 9, 10, 27, 38, 43, 82]

Output: [3, 9, 10, 27, 38, 43, 82]

Code in C

#include <stdio.h>

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


int n1 = mid - left + 1;
int n2 = right - mid;

// Create temporary arrays


int LeftArray[n1], RightArray[n2];

// Copy data to temporary arrays


for (int i = 0; i < n1; i++)
LeftArray[i] = arr[left + i];
for (int j = 0; j < n2; j++)
RightArray[j] = arr[mid + 1 + j];

// Merge the temporary arrays back into arr


int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (LeftArray[i] <= RightArray[j]) {
arr[k] = LeftArray[i];
i++;
} else {
arr[k] = RightArray[j];
j++;
}
k++;
}

// Copy remaining elements of LeftArray


while (i < n1) {
arr[k] = LeftArray[i];
i++;
k++;
}

// Copy remaining elements of RightArray


while (j < n2) {
arr[k] = RightArray[j];
j++;
k++;
}
}

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


if (left < right) {
int mid = left + (right - left) / 2;

// Recursively divide
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);

// Merge
merge(arr, left, mid, right);
}
}

int main() {
int arr[] = {38, 27, 43, 3, 9, 82, 10};
int size = sizeof(arr) / sizeof(arr[0]);

printf("Original array: ");


for (int i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
mergeSort(arr, 0, size - 1);

printf("Sorted array: ");


for (int i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");

return 0;
}

You might also like