🎓 Top 15 Udemy Courses (80-90% Discount): My Udemy Courses - Ramesh Fadatare — All my Udemy courses are real-time and project oriented courses.
▶️ Subscribe to My YouTube Channel (178K+ subscribers): Java Guides on YouTube
▶️ For AI, ChatGPT, Web, Tech, and Generative AI, subscribe to another channel: Ramesh Fadatare on YouTube
1. Introduction
Merge Sort is a divide-and-conquer algorithm that works by recursively splitting an array into two halves, sorting each half, and then merging the two sorted halves back together. It guarantees a time complexity of O(n log n), making it efficient for larger datasets.
2. Program Overview
In this program, we will:
1. Implement the merge function that merges two sorted halves of an array.
2. Implement the mergeSort function that recursively splits and sorts the array.
3. Sort an array of integers using Merge Sort.
4. Display the sorted array.
3. Code Program
#include <stdio.h>
// Merges two subarrays of arr[].
void merge(int arr[], int l, int m, int r) {
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
// create temporary 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++;
}
}
// Recursive function that sorts the array
void mergeSort(int arr[], int l, int r) {
if (l < r) {
int m = l + (r - l) / 2; // Find the middle point
mergeSort(arr, l, m); // Sort first half
mergeSort(arr, m + 1, r); // Sort second half
merge(arr, l, m, r); // Merge the sorted halves
}
}
// Function to print an array
void printArray(int arr[], int size) {
int i;
for (i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
// Driver code
int main() {
int arr[] = {38, 27, 43, 3, 9, 82, 10};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original array: \n");
printArray(arr, n);
mergeSort(arr, 0, n - 1);
printf("Sorted array: \n");
printArray(arr, n);
return 0;
}
Output:
Original array: 38 27 43 3 9 82 10 Sorted array: 3 9 10 27 38 43 82
4. Step By Step Explanation
1. The merge function is responsible for merging two sorted halves of an array. We copy the elements of the two halves into two temporary arrays L[] and R[]. We then iterate through L[] and R[], copying the smaller element of the two back into the original array.
2. The mergeSort function is a recursive function that splits the array into two halves, sorts each half by recursively calling itself, and then merges the two sorted halves using the merge function.
3. The printArray function is a utility function to display the elements of an array.
4. The main function initializes an array, prints it, sorts it using merge sort, and then prints the sorted array.
Merge Sort is particularly efficient for larger datasets and is used in many high-performance applications because of its predictable O(n log n) time complexity.
My Top and Bestseller Udemy Courses. The sale is going on with a 70 - 80% discount. The discount coupon has been added to each course below:
Build REST APIs with Spring Boot 4, Spring Security 7, and JWT
![[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25](https://img-c.udemycdn.com/course/750x422/6852721_b512_2.jpg "[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25")
[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25
ChatGPT + Generative AI + Prompt Engineering for Beginners
Spring 7 and Spring Boot 4 for Beginners (Includes 8 Projects)
Available in Udemy for Business
Building Real-Time REST APIs with Spring Boot - Blog App
Available in Udemy for Business
Building Microservices with Spring Boot and Spring Cloud
Available in Udemy for Business
Java Full-Stack Developer Course with Spring Boot and React JS
Available in Udemy for Business
Build 5 Spring Boot Projects with Java: Line-by-Line Coding
Testing Spring Boot Application with JUnit and Mockito
Available in Udemy for Business
Spring Boot Thymeleaf Real-Time Web Application - Blog App
Available in Udemy for Business
Master Spring Data JPA with Hibernate
Available in Udemy for Business
Spring Boot + Apache Kafka Course - The Practical Guide
Available in Udemy for Business
Comments
Post a Comment
Leave Comment