C Online Compiler
Example: Merge Sort using Divide and Conquer in C
C
C++
C#
Java
Python
PHP
main.c
STDIN
Run
// Merge Sort using Divide and Conquer #include <stdio.h> #include <stdlib.h> // For malloc and free // Function to merge two subarrays of arr[] // First subarray is arr[left..mid] // Second subarray is arr[mid+1..right] void merge(int arr[], int left, int mid, int right) { int i, j, k; int n1 = mid - left + 1; int n2 = right - mid; // Create temporary arrays int *L = (int*) malloc(n1 * sizeof(int)); int *R = (int*) malloc(n2 * sizeof(int)); // Copy data to temp 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 temp arrays back into arr[left..right] i = 0; // Initial index of first subarray j = 0; // Initial index of second 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 the remaining elements of L[], if any while (i < n1) { arr[k] = L[i]; i++; k++; } // Copy the remaining elements of R[], if any while (j < n2) { arr[k] = R[j]; j++; k++; } // Free the dynamically allocated memory free(L); free(R); } // Function to recursively sort the array using mergeSort void mergeSort(int arr[], int left, int right) { if (left < right) { // Find the middle point int mid = left + (right - left) / 2; // Sort first and second halves mergeSort(arr, left, mid); mergeSort(arr, mid + 1, right); // Merge the sorted halves merge(arr, left, mid, right); } } // Utility 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 program to test the merge sort implementation int main() { int arr[] = {38, 27, 43, 3, 9, 82, 10}; int n = sizeof(arr) / sizeof(arr[0]); printf("Given array is \n"); printArray(arr, n); mergeSort(arr, 0, n - 1); printf("Sorted array is \n"); printArray(arr, n); return 0; }
Output
Clear
ADVERTISEMENTS