Merge Sort vs Quick Sort in C: Key Differences and Code Examples
Merge Sort is a stable sorting algorithm with guaranteed O(n log n) time complexity, while Quick Sort is generally faster on average but can degrade to O(n²) in the worst case. Merge Sort uses extra memory for merging, whereas Quick Sort sorts in place with less memory overhead.Quick Comparison
Here is a side-by-side comparison of Merge Sort and Quick Sort based on key factors:
| Factor | Merge Sort | Quick Sort |
|---|---|---|
| Algorithm Type | Divide and conquer, stable | Divide and conquer, unstable |
| Time Complexity (Average) | O(n log n) | O(n log n) |
| Time Complexity (Worst) | O(n log n) | O(n²) |
| Space Complexity | O(n) extra space | O(log n) extra space |
| Stability | Stable (preserves order) | Unstable |
| Typical Use Case | When stability is needed or worst-case matters | When average speed and low memory are preferred |
Key Differences
Merge Sort always divides the array into two halves, sorts them recursively, and then merges the sorted halves. This merging step requires extra memory proportional to the array size, making it less memory efficient but stable, meaning equal elements keep their original order.
Quick Sort selects a pivot element and partitions the array so that elements less than the pivot come before it and greater elements come after. It then recursively sorts the partitions. It sorts in place, using less memory, but its worst-case time complexity is O(n²) if the pivot choices are poor. It is generally faster on average due to better cache performance.
In summary, Merge Sort guarantees consistent performance and stability at the cost of extra memory, while Quick Sort is faster and uses less memory but can be unstable and slower in worst cases.
Code Comparison
Below is a C implementation of Quick Sort to sort an integer array:
#include <stdio.h> void swap(int* a, int* b) { int temp = *a; *a = *b; *b = temp; } int partition(int arr[], int low, int high) { int pivot = arr[high]; int i = low - 1; for (int j = low; j < high; j++) { if (arr[j] < pivot) { i++; swap(&arr[i], &arr[j]); } } swap(&arr[i + 1], &arr[high]); return i + 1; } void quickSort(int arr[], int low, int high) { if (low < high) { int pi = partition(arr, low, high); quickSort(arr, low, pi - 1); quickSort(arr, pi + 1, high); } } int main() { int arr[] = {10, 7, 8, 9, 1, 5}; int n = sizeof(arr) / sizeof(arr[0]); quickSort(arr, 0, n - 1); for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } return 0; }
Merge Sort Equivalent
Here is a C implementation of Merge Sort sorting the same integer array:
#include <stdio.h> #include <stdlib.h> void merge(int arr[], int l, int m, int r) { int n1 = m - l + 1; int n2 = r - m; int* L = (int*)malloc(n1 * sizeof(int)); int* R = (int*)malloc(n2 * sizeof(int)); for (int i = 0; i < n1; i++) L[i] = arr[l + i]; for (int j = 0; j < n2; j++) R[j] = arr[m + 1 + j]; int i = 0, j = 0, k = l; while (i < n1 && j < n2) { if (L[i] <= R[j]) { arr[k++] = L[i++]; } else { arr[k++] = R[j++]; } } while (i < n1) { arr[k++] = L[i++]; } while (j < n2) { arr[k++] = R[j++]; } 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[] = {10, 7, 8, 9, 1, 5}; int n = sizeof(arr) / sizeof(arr[0]); mergeSort(arr, 0, n - 1); for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } return 0; }
When to Use Which
Choose Merge Sort when you need a stable sort or when worst-case performance must be guaranteed, such as in real-time systems or when sorting linked lists. It is also preferred when working with large datasets that do not fit entirely in memory because it can be adapted for external sorting.
Choose Quick Sort when average speed and low memory usage are priorities, such as in general-purpose sorting of arrays in memory. It is usually faster in practice due to better cache locality, but be cautious with inputs that may cause worst-case behavior.