--- title: "Merge sort algorithm and trace" subject: "Data Structure and Algorithm" chapter: 7 key: "semester_4/data_structure_and_algorithm:merge-sort-algorithm-trace" source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/merge-sort-algorithm-trace site: BCT Engineering --- # Merge sort algorithm and trace Data Structure and Algorithm ยท Chapter 7: Sorting - Asked in: 2071 Bhadra, 3+5 marks - Video: [Learn Merge Sort in 13 minutes ๐Ÿ”ช](https://www.youtube.com/watch?v=3j0SWDX4AtU) โ€” Bro Code - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/merge-sort-algorithm-trace - Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-7 ## Question Discuss the algorithm merge sort. Show the steps to sort the data 5, 2, 4, 6, 1, 3, 2, 6 using merge sort. ## Short answer Merge sort divides the array into halves recursively, then merges sorted halves. For 5,2,4,6,1,3,2,6: splitting yields single elements. Merging pairs: [5]&[2]โ†’2,5; [4]&[6]โ†’4,6; [1]&[3]โ†’1,3; [2]&[6]โ†’2,6. Merging halves: [2,5]&[4,6]โ†’2,4,5,6; [1,3]&[2,6]โ†’1,2,3,6. Final merge: 1,2,2,3,4,5,6,6. ## Answer Merge sort is a divide-and-conquer sorting algorithm. It divides the array into two halves, sorts each half recursively, and merges the two sorted halves into one sorted array. #### Algorithm ```text MERGESORT(a, low, high) 1. if low < high 2. mid = (low + high) / 2 3. MERGESORT(a, low, mid) // sort left half 4. MERGESORT(a, mid+1, high) // sort right half 5. MERGE(a, low, mid, high) // combine ``` MERGE copies the smaller of the two front elements into a temporary array, repeatedly, until one half is exhausted, then copies the rest of the other half, and finally copies the temporary array back. ```c void merge(int a[], int lo, int mid, int hi) { int t[100], i = lo, j = mid + 1, k = 0; while (i <= mid && j <= hi) t[k++] = (a[i] <= a[j]) ? a[i++] : a[j++]; while (i <= mid) t[k++] = a[i++]; while (j <= hi) t[k++] = a[j++]; for (k = 0, i = lo; i <= hi; i++, k++) a[i] = t[k]; } void mergeSort(int a[], int lo, int hi) { if (lo < hi) { int mid = (lo + hi) / 2; mergeSort(a, lo, mid); mergeSort(a, mid + 1, hi); merge(a, lo, mid, hi); } } ``` **Complexity:** T(n) = 2T(n/2) + O(n), so best, average and worst cases are all O(n log n). It needs O(n) extra space and is stable. #### Trace for 5, 2, 4, 6, 1, 3, 2, 6 ```text 5 2 4 6 1 3 2 6 5 2 4 6 | 1 3 2 6 5 2 | 4 6 | 1 3 | 2 6 5 | 2 | 4 | 6 | 1 | 3 | 2 | 6 ``` | Step | Merge | Result | |---|---|---| | 1 | [5] + [2] | [2, 5] | | 2 | [4] + [6] | [4, 6] | | 3 | [1] + [3] | [1, 3] | | 4 | [2] + [6] | [2, 6] | | 5 | [2, 5] + [4, 6] | [2, 4, 5, 6] | | 6 | [1, 3] + [2, 6] | [1, 2, 3, 6] | | 7 | [2, 4, 5, 6] + [1, 2, 3, 6] | [1, 2, 2, 3, 4, 5, 6, 6] | **Answer: 1, 2, 2, 3, 4, 5, 6, 6** ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. Merge sort is based on which approach? A. Greedy B. Divide and conquer C. Dynamic programming D. Distribution into buckets Answer: B. It divides, sorts halves recursively and merges. (Key point: Paradigm) 2. What recurrence gives merge sort's time? A. T(n) = T(n-1) + n B. T(n) = 2T(n/2) + O(n), so O(n log n) in all cases C. T(n) = T(n/2) + 1 D. T(n) = 2T(n-1) Answer: B. Two half-size calls plus an O(n) merge. (Key point: Recurrence) 3. How does MERGE work? A. It copies the smaller of the two front elements to a temp array until one half is exhausted, then copies the rest B. It swaps the two halves C. It picks a pivot D. It sorts using heaps Answer: A. Then the temp array is copied back. (Key point: Merge step) 4. What extra space does merge sort need? A. O(1) B. O(log n) only C. O(n) D. O(n^2) Answer: C. A temporary array is needed; it is stable. (Key point: Space) ## Related in Data Structure and Algorithm - [Merge sort on 85, 76, 46, 92, ...](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Amerge-sort-trace-85-76) โ€” Data Structure and Algorithm, chapter 7 - [Merge and radix sort on 142, 523, ...](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Amerge-radix-trace-142) โ€” Data Structure and Algorithm, chapter 7 - [Merge sort on 47, 27, 56, 23, ...](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Amerge-sort-trace-47-27) โ€” Data Structure and Algorithm, chapter 7 - [Selection sort with trace](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aselection-sort-explain-trace) โ€” Data Structure and Algorithm, chapter 7 - [Algorithm for an exchange sort](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aexchange-sort-algorithm) โ€” Data Structure and Algorithm, chapter 7, asked 2ร— - [Radix sort definition and algorithm](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aradix-sort-algorithm) โ€” Data Structure and Algorithm, chapter 7 ## Related in other subjects - [Short note: Routing algorithm in data communication](https://www.bctengineer.com/question.md?key=semester_8%2Ftelecommunications%3Arouting-algorithm-data-comm) โ€” Telecommunications, chapter 8, asked 2ร— - [Total station features and data recording steps](https://www.bctengineer.com/question.md?key=semester_4%2Fsurveying_ii%3Atotal-station-features-data-recording) โ€” Surveying II, chapter 9