Briefly discuss the approach you would take to the following programming scenarios. Make any assumptions you need to. There are no “right” answers for any of these questions.

1. You have a large, singly-linked list that needs to be sorted. How would you do this efficiently?

Ideas presented:

Convert the list to an array then use QuickSort or any other favorite fast sort.

- Utilizes the speed that arrays provide.

- Memory costs might be an issue. If the array is large, the additional memory might be too much.

- Just using pointers to the items in the list might alleviate this cost, but remember that each pointer is itself 4 bytes.

Use an insertion sort on the list.

- Fits in well with the idea of a list and traversing it.

- Could potentially be quadratic.

- One improvement: place some “bookmark” pointers along the way. When trying to find where to insert the next item, instead of traversing the whole list, first traverse the bookmarks to get you in the general vicinity.

Merge Sort:

- Merging two linked-lists is easily done.

- To split the list requires traversing the list. Possibly consider other means of splitting (see the book).

Quick Sort

- One issue is having to move backwards through the list. The ability to use quicksort my warrant this additional memory cost.

- Another issue is finding the pivot. Using the first element is cheap and easy.

2. You are presented with two mergesort routines, MSORT1 and MSORT2. For small lists, both perform the same. For larger lists, however, MSORT2 significantly outperforms MSORT1. Comparing the code of the two routines, you find that both use roughly the same number of machine instructions. What could possibly be the difference that makes MSORT2 perform better than MSORT1?

Ideas presented:

The depth of the recursion
In-place vs. not in-place
MSORT1 uses more costly machine instructions
Dynamic memory cleanup
Cache use