- 2072 Asoj · 3 marks
Merge sort on 85, 76, 46, 92, ...
Short answer
Using merge sort, recursively divide 85,76,46,92,30,41,12 into single elements. Merge stepwise: [85]&[76]→76,85; [46]&[92]→46,92; [30]&[41]→30,41; then merge [76,85]&[46,92]→46,76,85,92; merge [30,41]&[12]→12,30,41; final merge yields 12,30,41,46,76,85,92.
Trace the steps to sort the following set of data using merge sort: 85, 76, 46, 92, 30, 41 and 12.
Merge sort uses divide and conquer: split the list into two halves until each part has one element, then merge the sorted parts pairwise. Here the left half gets the extra element when the size is odd.
Dividing
85 76 46 92 30 41 12
85 76 46 92 | 30 41 12
85 76 | 46 92 | 30 41 | 12
85 | 76 | 46 | 92 | 30 | 41 | 12
Merging
| Step | Merge | Result |
|---|---|---|
| 1 | [85] + [76] | [76, 85] |
| 2 | [46] + [92] | [46, 92] |
| 3 | [30] + [41] | [30, 41] |
| 4 | [76, 85] + [46, 92] | [46, 76, 85, 92] |
| 5 | [30, 41] + [12] | [12, 30, 41] |
| 6 | [46, 76, 85, 92] + [12, 30, 41] | [12, 30, 41, 46, 76, 85, 92] |
Answer: 12, 30, 41, 46, 76, 85, 92
✓ Answer checked by Claude Opus 5.5 (high effort)
Related questions
- Merge sort algorithm and trace · Data Structure and Algorithm, chapter 7
- Merge and radix sort on 142, 523, ... · Data Structure and Algorithm, chapter 7
- Merge sort on 47, 27, 56, 23, ... · Data Structure and Algorithm, chapter 7
- Heap sort on 37, 33, 26, 92, ... · Data Structure and Algorithm, chapter 7
- Shell sort on 92, 83, 22, 49, ... · Data Structure and Algorithm, chapter 7
- Selection sort with trace · Data Structure and Algorithm, chapter 7
- Power output with 46.85 kV sending, 33 kV receiving · Power System Analysis I, chapter 6
- Gumbel design flood, 43 years data, 85% reliability · Engineering Hydrology, chapter 6 · asked 2×
- GVF in 12 m wide channel, 2 steps · Hydraulics, chapter 8
- Line spectra of 12 + 6sin(140πt+30°) - 9cos(80πt-70°) · Data Communication, chapter 3