slog finale on sorting algorithm

How time flies! Here comes the final week of class and also my slog finale.

Compared with recursion, I find sorting a easier part in 148 that follow smoothly from 108. In 108, we learnt three simple but less efficient sorting algorithms. Apart from a revision, we are also introduced merge, quick and count sort. I have explained merge and quick sort in detail in the previous two slog entries. As for count sort, it is significantly efficient when the given numbers are within a certain range. It basically records the occurrences of each number in its corresponding position in a new list. Then output a sorted list according to the sequence and occurrence of numbers.

Surprisingly, in last week's lab, according to the graph we plot, insertion sort is less efficient than selection sort. I thought insertion has a best sase and a worst case while selection need to do all the comparisons, and it seems that the result is contrary to what I expected. A possible explanation to this question might be that insertion involves shifting each item behind the insertion point backwards while selection only need to change the items in two positions. Thus, they take different amount of time for shifting and exchanging values.

In addition, we were making small adjustments to the existing sorting codes to improve efficiency. For example, in merge, replacing "while L1[i1:] and L2[i2:]" with "i1 < len(L1) and i2 < len(L2)" could make a great difference because each time L[:a] is a linear copy of the list which takes O(n) time. As guided in the last lab, avoid redundancy is one way to improve efficiency.

To understand sorting, it is useful to compare the number of division AND comparison in order to analyze efficiency. The practical example would be the last in the second midterm, of which i gain insights from merge sort and quick sort.



Question:
1. why would in place be faster than creating a new list?
2. what about collision? if we have fifty percent chance of collision after 23 items, how long a list do we need? how does probing a list works?