Scribd
Upload
4 views3 pages

Lecture Notes - Merge Sort

Merge Sort is a comparison-based sorting algorithm that utilizes the Divide and Conquer strategy, achieving a time complexity of O(n log n) and a space complexity of O(n). The algorithm works by recursively splitting the array into halves, sorting them, and merging the sorted halves back together. An implementation example in C is provided, demonstrating the sorting of an array through the merge process.

Uploaded by

nandhana20zero4
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
4 views3 pages

Lecture Notes - Merge Sort

Merge Sort is a comparison-based sorting algorithm that utilizes the Divide and Conquer strategy, achieving a time complexity of O(n log n) and a space complexity of O(n). The algorithm works by recursively splitting the array into halves, sorting them, and merging the sorted halves back together. An implementation example in C is provided, demonstrating the sorting of an array through the merge process.

Uploaded by

nandhana20zero4
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

Lecture Notes: Merge Sort

Overview: Merge Sort is an efficient, general-purpose, comparison-based sorting algorithm. It is


a classic example of the Divide and Conquer paradigm. It divides the input array into two
halves, calls itself for the two halves, and then merges the two sorted halves.

1. Concept and Mechanism


●​ Algorithmic Strategy: Divide and Conquer
●​ Time Complexity: Best, Worst, and Average Case: O(n log n)
●​ Space Complexity: O(n) (Requires auxiliary space for merging)
●​ Stability: Stable (Preserves the relative order of equal elements)

2. Detailed Step-by-Step Example


Let's trace how Merge Sort logically breaks down and recombines an array: [38, 27, 43, 3, 9, 82,
10].

Phase Operation Array / Subarray


Representation

Divide Initial Split [38, 27, 43, 3] | [9, 82, 10]

Divide Sub-splits [38, 27] | [43, 3] [9,


82] | [10]

Divide Individual Elements [38] [27] [43] [3]


[9] [82] [10]

Conquer & Merge Merge pairs [27, 38] | [3, 43] [9,
82] | [10]

Conquer & Merge Merge halves [3, 27, 38, 43] [9,
10, 82]

Final Merge Combine to Sorted Array [3, 9, 10, 27, 38, 43, 82]

3. Implementation in C
#include <stdio.h>​
#include <stdlib.h>​
​
void merge(int arr[], int l, int m, int r) {​
int i, j, k;​
int n1 = m - l + 1;​
int n2 = r - m;​
​
int *L = (int *)malloc(n1 * sizeof(int));​
int *R = (int *)malloc(n2 * sizeof(int));​
​
for (i = 0; i < n1; i++) L[i] = arr[l + i];​
for (j = 0; j < n2; j++) R[j] = arr[m + 1 + j];​
​
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++;​
}​
​
while (i < n1) {​
arr[k] = L[i];​
i++; k++;​
}​
while (j < n2) {​
arr[k] = R[j];​
j++; k++;​
}​
free(L);​
free(R);​
}​
​
void mergeSort(int arr[], int l, int r) {​
if (l < r) {​
int m = l + (r - l) / 2;​
mergeSort(arr, l, m);​
mergeSort(arr, m + 1, r);​
merge(arr, l, m, r);​
}​
}​
​
int main() {​
int arr[] = {38, 27, 43, 3, 9, 82, 10};​
int arr_size = sizeof(arr) / sizeof(arr[0]);​
mergeSort(arr, 0, arr_size - 1);​
printf("Sorted array: \n");​
for (int i = 0; i < arr_size; i++) printf("%d ", arr[i]);​
return 0;​
}​

You might also like