Consider the algorithms for merge sort, insertion sort and counting sort as disc
ID: 3805122 • Letter: C
Question
Consider the algorithms for merge sort, insertion sort and counting sort as discussed in class. For each of the following sets of circumstances, select which sort would be the most appropriate choice. Base your choice on the data given without further assumptions. 5. [5 pts.) The sort needs to be as fast as possible. The input data is random, and can be any 64-bit integer. There is sufficient memory available for any of the three options. 6. [5 pts.] The sort needs to be as fast as possible. Valid input values are in dollars-and-cents, and never greater than 1,000,000.00. There is sufficient memory available for any of the three options. 7. [5 pts.l The sort needs to be as fast as possible. The input data is random, and can be any 64-bit integer. Memory is restricted. In terms of memory usage the sort must be "in-place" or better (O(n) memory requiremen). 8. [5 pts.] The amount of data to be sorted is enormous, and it is preferable not to store the entire data set in memory. There is a straight-forward mapping of the values to be sorted to the integers values -1000 to 1000. 9. [5 pts.] The data are relatively stable and consist of about 100,000 items. Each night, when the users are offline, the dataset is updated to add at most 3 new data items. The data values can be considered as random integers.Explanation / Answer
9) Insertion sort is the fastest here. In insertion sort in each iteration we already have a sorted part of tha array and the unsorted value are put in their appropriate positions. So as the data is relatively stable and at max 3 values are updated. So we only need to worry about that 3 values, because the rest of the values are already sorted.