Merge Sort Algorithm - Interactive Learning
Master Merge Sort - DSA Learning Platform 🔀 Merge Sort Intermediate O(n log n) Master the divide-and-conquer sorting algorithm with guaranteed O(n log n) performance 📖 Understanding Merge Sort Concept Algorithm Complexity Use Cases What is Merge Sort? Merge Sort is an efficient, stable, divide-and-conquer sorting algorithm. It divides the input array into two halves, recursively sorts them, and then merges the two sorted halves to produce the final sorted array. The key insight is that merging two sorted arrays into one sorted array is very efficient - it takes O(n) time. By recursively dividing and merging, we achieve O(n log n) overall complexity. 🔑 Key Characteristics Divide and Conquer approach Stable sort (preserves order of equal elements) Guaranteed O(n log n) - no worst case degradation Requires O(n) auxiliary space Excellent for linked lists (no extra space needed) Parallelizable - subarrays can be sorted independently Divide and Conquer Visualization [38, 27, 43, 3, 9, 82, 10] ↓ DIVIDE [38, 27, 43, 3] [9, 82, 10] ↓ ↓ [38, 27] [43, 3] [9, 82] [10] ↓ ↓ ↓ ↓ [38] [27] [43] [3] [9] [82] [10] ↓ ↓ ↓ ↓ [27, 38] [3, 43] [9, 82] [10] ↓ ↓ [3, 27, 38, 43] [9, 10, 82] ↓ MERGE [3, 9, 10, 27, 38, 43, 82] Algorithm Steps 1. Divide: Split the array into two halves. 2. Conquer: Recursively sort each half. 3. Combine: Merge the two sorted halves into one sorted array. Base Case: An array of size 0 or 1 is already sorted. 🔄 Merge Process Compare elements from both halves Pick the smaller element Move to next element in that half Repeat until all elements are merged Pseudocode procedure mergeSort(A, left, right) if left < right then mid = (left + right) / 2 // Recursively sort both halves mergeSort(A, left, mid) mergeSort(A, mid + 1, right) // Merge sorted halves merge(A, left, mid, right) end if end procedure procedure merge(A, left, mid, right) // Create temp arrays L = A[left..mid] R = A[mid+1..right] // Merge back into A i = 0, j = 0, k = left while i < |L| and j < |R| do if L[i]
Subject: Data Structures with Animation | Chapter: Sorting Algorithms with Animation