Suppose that we run a sorting algorithm on an array that is already sorted. How many array writes will it perform if we use each of the following algorithms? An answer in big-O notation is acceptable.
bubble sort
selection sort
insertion sort
In a selection sort of an array with N elements, what is the maximum number of times that an element might move to a new position?
Suppose that we run an insertion sort on an input array whose values are all 0 or 1. The array contains N values.
a) What will be the worst-case running time?
b) What will be the expected (i.e. average) running time, if the values in the input array are in a random order?
Suppose that we run merge sort on an array that contains N elements. (If you like, you may assume that N is a power of 2.)
a) How many times will each array element be copied to a different memory location during the course of the sort?
b) How many array writes will the sort perform in all?
c) Does the running time of merge sort depend on the initial arrangement of the values that are being sorted? In particular, is it more efficient when run on an input array that is already sorted?
Consider the merge sort implementation that we saw in the lecture.
a) If we use it to sort an array that occupies N bytes of memory, what is the largest amount of additional memory that will be required at any moment during the sorting process? (Assume that any temporary arrays are freed as soon as there are no more references to them.)
b) Is it possible to modify our implementation to reduce this memory requirement?