Comment on page
- 1.What happens when a Java file is compiled? HINT: Think about
- 2.Why can a block of code run faster the second time it executes as compared to the first time?
- 3.What's the optimal way to sort an array of integers? Assume the integers are uniformly randomly distributed.
- 1.Under what conditions would LSD sort be faster than mergesort?
There are two main cases when LSD sort is much faster than mergesort: when there are a large number of strings (large N), and when all strings are very similar to each other.
When N is really large, we see the asymptotic behavior of LSD sort beat the asymptotic behavior of merge sort, which is slower with a runtime of
When the strings are very similar, then each comparison in merge sort is slow, roughly linear time in the length of the string. Instead of comparing each letter in each string at every merge, LSD only examines the letters of each string once.