Give an example of an o( n log2 n sort. Is the sort you have named a stable sort
ID: 3599240 • Letter: G
Question
Give an example of an o( n log2 n sort. Is the sort you have named a stable sort or an unstable sort? In radix sort for sort the running time is a function of the size of the field to be sorted. Given that you want to sort a fixed length field at what length of field will an 0(n log2 n) sort be more efficient than a radix sort for a group of 16384 records? Show your work! You need to sort the names of the 50 states in the United States into alphabetical order. Which sort would you use? Explain whyExplanation / Answer
Merge sort is an example of O(nlog2n). Merge Sort is stable by nature.
Comparison Table:
Input Size (n)
O(nlog2n)
Radix Sort(16348)
32
32*5=160
32
1024
1024*10=10240
1024
4096
4096*12=
16348(<49152)
2048
2048*11=22528
16348(<22548)
1536
1536*10.58
16348(>16250)
1556
1556*10.60
16348(>16493)
1543
1543*10.59
16348(>16340)
There is approximately input size is 1543 for merge sort in comparison of radix sort takes as input size 16348.
To sort the names of states of United state Bucket sort can be used. The bucket size will be 26 (Name of states can start anyone from the twenty-six alphabets), then insertion sort can be applied to sort the names in each bucket and finally union the elements of the buckets.
Input Size (n)
O(nlog2n)
Radix Sort(16348)
32
32*5=160
32
1024
1024*10=10240
1024
4096
4096*12=
16348(<49152)
2048
2048*11=22528
16348(<22548)
1536
1536*10.58
16348(>16250)
1556
1556*10.60
16348(>16493)
1543
1543*10.59
16348(>16340)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.