Average-case performance of sorting algorithms Our analyses of sorting algorithms in this chapter focused on worst-case performance. Mesh sorting algorithms that are asymptotically optimal in terms of...

Average-case performance of sorting algorithms

Our analyses of sorting algorithms in this chapter focused on worst-case performance. Mesh sorting algorithms that are asymptotically optimal in terms of their worst-case performance are clearly also optimal in terms of their average-case performance when applied to randomly ordered key values. Show that the average-case performance of shearsort is also asymptotically the same as its worst-case performance. Hint: Consider what happens to the k smallest keys as shearsort runs on a k × k mesh.