Quickersort, Straight Insertion Sort, Mehlhorn's AVL-tree Sorting Algorithm and Cook's new sorting algorithm are compared on nearly and nedium sorted lists. The ratio of the minimum number of list elements that must be removed so that the remaining portion of the list is in order to the size of the...