--- title: "Merge and radix sort on 142, 523, ..." subject: "Data Structure and Algorithm" chapter: 7 key: "semester_4/data_structure_and_algorithm:merge-radix-trace-142" source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/merge-radix-trace-142 site: BCT Engineering --- # Merge and radix sort on 142, 523, ... Data Structure and Algorithm · Chapter 7: Sorting - Asked in: 2071 Magh, 8 marks - 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-radix-trace-142 - Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-7 ## Question Trace the sorting steps in merge sort and radix sort for sorting the data 142, 523, 228, 375, 462, 198, 249, 144, 123 in ascending order. ## Short answer Merge sort: recursive division, then merge steps produce 123,142,144,198,228,249,375,462,523. Radix sort: 3 passes: after units: 142,462,523,123,144,375,228,198,249; after tens: 523,123,228,142,144,249,462,375,198; after hundreds (leading zeros for 2-digit numbers): 123,142,144,198,228,249,375,462,523. ## Answer #### Merge sort on 142, 523, 228, 375, 462, 198, 249, 144, 123 Split (left half gets the extra element): ```text 142 523 228 375 462 | 198 249 144 123 142 523 228 | 375 462 | 198 249 | 144 123 142 523 | 228 | 375 | 462 | 198 | 249 | 144 | 123 142 | 523 ``` Merge: | Step | Merge | Result | |---|---|---| | 1 | [142] + [523] | [142, 523] | | 2 | [142, 523] + [228] | [142, 228, 523] | | 3 | [375] + [462] | [375, 462] | | 4 | [142, 228, 523] + [375, 462] | [142, 228, 375, 462, 523] | | 5 | [198] + [249] | [198, 249] | | 6 | [144] + [123] | [123, 144] | | 7 | [198, 249] + [123, 144] | [123, 144, 198, 249] | | 8 | [142, 228, 375, 462, 523] + [123, 144, 198, 249] | [123, 142, 144, 198, 228, 249, 375, 462, 523] | #### Radix sort on the same data (3 digits, so 3 passes) **Pass 1 (units digit)** | Queue | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |---|---|---|---|---|---|---|---|---|---|---| | Keys | | | 142, 462 | 523, 123 | 144 | 375 | | | 228, 198 | 249 | List: 142, 462, 523, 123, 144, 375, 228, 198, 249 **Pass 2 (tens digit)** | Queue | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |---|---|---|---|---|---|---|---|---|---|---| | Keys | | | 523, 123, 228 | | 142, 144, 249 | | 462 | 375 | | 198 | List: 523, 123, 228, 142, 144, 249, 462, 375, 198 **Pass 3 (hundreds digit)** | Queue | 0 | 1 | 2 | 3 | 4 | 5 | 6-9 | |---|---|---|---|---|---|---|---| | Keys | | 123, 142, 144, 198 | 228, 249 | 375 | 462 | 523 | | **Answer: 123, 142, 144, 198, 228, 249, 375, 462, 523** ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. In the trace, how is an odd-sized list split? A. Right half gets the extra element B. Left half gets the extra element C. Pivot at the center D. It is not split Answer: B. The first 5 of 9 elements form the left half. (Key point: Merge splitting) 2. How many radix passes does 142...123 need? A. 3, one per digit B. 9, one per key C. 10 D. 1 Answer: A. Max key 523 has 3 digits. (Key point: Radix passes) 3. After the units-digit pass, which queue holds 142 and 462? A. Queue 2 B. Queue 4 C. Queue 1 D. Queue 3 Answer: A. Both end in digit 2, kept in input order. (Key point: Radix pass 1) 4. What is the sorted result by both methods? A. 123, 142, 144, 198, 228, 249, 375, 462, 523 B. 123, 142, 144, 228, 198, 249, 375, 462, 523 C. 142, 123, 144, 198, 228, 249, 375, 462, 523 D. 523, 462, 375, 249, 228, 198, 144, 142, 123 Answer: A. Ascending order. (Key point: Result) ## Related in Data Structure and Algorithm - [Merge sort algorithm and trace](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Amerge-sort-algorithm-trace) — 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 - [Radix sort on 25, 57, 48, 37, ...](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aradix-sort-25-57-48) — Data Structure and Algorithm, chapter 7 - [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 - [Radix sort on 345, 654, 924, ...](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aradix-sort-345-654) — Data Structure and Algorithm, chapter 7 - [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 - [Sort array ascending in FORTRAN](https://www.bctengineer.com/question.md?key=semester_1%2Fcomputer_programming%3Afortran-sort-ascending) — Computer Programming, chapter 11, asked 2× - [Sort employee structures by salary](https://www.bctengineer.com/question.md?key=semester_1%2Fcomputer_programming%3Astruct-employee-sort-salary) — Computer Programming, chapter 8, asked 2× - [Employee text file; sort into binary file](https://www.bctengineer.com/question.md?key=semester_1%2Fcomputer_programming%3Afile-employee-sorted-binary) — Computer Programming, chapter 10 - [Conductor selection, 100 MW 70 km 132 kV](https://www.bctengineer.com/question.md?key=semester_8%2Ftransmission_and_distribution_system_design%3Aconductor-selection-100mw-70km-132kv) — Transmission and Distribution System Design, chapter 4