Sorting Runtimes

Question 1

What is Quicksorts best, worst and average runtimes? Is it stable and in-place?

Answer 1

Best: n log n

Worst: n²

Average: n log n

Stable: Not stable but can be

In-place: Yes

note:

• stable means to not have the order of 2 equal keys changed i.e. if 5D and 5H were in the initial input array in this order the output array should always hold 5D and 5H one after the other (not 5H, 5D)
• in-place means to output, for example, an array of the same size as the input and thus not wasting memory.

If the list is implemented as an array, this can be done in-place and with at most n comparisons

Question 2

What is Merge Sorts best, worst and average runtimes? Is it stable and in-place?

Answer 2

Best, worst and avg are all

n log n

Stable: Mostly

In-place: No

In any case the number of comparisons is in Θ(n)

Question 3

What is Heap Sorts best, worst and average runtimes? Is it stable and in-place?

Answer 3

Best, worst and avg are all

n log n

Stable: No

In-place: Sure?

Question 4

What is BubbleSorts best, worst and average runtimes? Is it stable and in-place?

Answer 4

Best: n

Worst: n²

Avg: n²

Stable: Yes

In-place: Yes

Question 5

What is Insertion Sorts best, worst and average runtimes? Is it stable and in-place?

Answer 5

Best: n

Worst: n²

Avg: n²

Stable: Yes

In-place: Yes

• It works well on small lists, or lists that are nearly sorted*
• number of inversions is n(n − 1)/2 in the worst case ​*(where input is in reverse sorted order)
• 0 in the best case (input is already sorted)*
• about n(n − 1)/4 on average case*

Question 6

What is Selection Sorts best, worst and average runtimes? Is it stable and in-place?

Answer 6

Best, worst and avg are all

n²

Stable: No

In-place: Yes

In practice, it is not as fast as insertion sort

Question 7

Shell Sort

Answer 7

Almost nothing is known about average-case running time of Shellsort.

O(n 7/6 ) avg case

Values of h chosen from all relevant numbers of the form 2 i3 j have been proved to give O(n(log n) 2 ) running time

Question 8

Mergesort recurrence I

Answer 8

C(n) = 2C(n/2) + n

= 2(2C(n/4) + n/2) + n

= 4C(n/4) + 2n = . . .

= 2^kC(1) + kn

= n lg n.

Question 9

Quicksort recurrence

Answer 9

Θ(nlogn)

if 1/n instead of 2/n we get

Θ(nl)