Merge Sort (Divide & Conquer)
Visualize the divide and conquer approach of merge sort with step-by-step breakdown
Merge Sort (Divide & Conquer)
Merge Sort is a divide-and-conquer algorithm that divides the array into halves, sorts them separately, and then merges them back together in sorted order.
Theory & Concepts
Definition:
Merge Sort follows the divide-and-conquer paradigm: divide the problem into smaller subproblems, solve them independently, and combine the solutions to solve the original problem.
Key Points:
- Stable sorting algorithm - maintains relative order of equal elements
- Guaranteed O(n log n) time complexity in all cases
- Requires O(n) extra space for merging
- Recursive approach with clear divide and conquer steps
Applications:
- External sorting for large datasets
- Merge operations in database systems
- Parallel processing and distributed computing
- Foundation for other divide-and-conquer algorithms
University Guidelines
Exam Weightage
6-8 marks MarksSyllabus Coverage:
- Divide and conquer paradigm
- Merge sort algorithm implementation
- Recurrence relation analysis
- Time and space complexity
- Comparison with other sorting algorithms
Common Questions:
- Implement merge sort algorithm
- Analyze time complexity using recurrence
- Compare merge sort with quick sort
- Trace execution for given array
Exam Tips:
Draw recursion tree for complexity analysis
Show merge process step by step
Remember T(n) = 2T(n/2) + O(n) recurrence
Highlight stable sorting property
Algorithm Details
O(n log n) - all cases
Time Complexity
O(n) for temporary arrays
Space Complexity
Algorithm Steps:
- 1Divide array into two halves
- 2Recursively sort left half
- 3Recursively sort right half
- 4Merge the two sorted halves
- 5Return the merged sorted array
Input Array
💡 Enter numbers separated by commas. Example: 5, 2, 8, 1, 9
✓Current Array (7 elements):
64
34
25
12
22
11
90