Sorting, Sets and Selection (notes)

Merge-Sort and Quick-Sort are based on recursion in and algorithmic design pattern called divide-and-conquer, and O(nlogn) time bound is the best possible for a comparison-based sorting algorithm.

Divide-and-Conquer:

1. Divide: if the input size is smaller than a certain threshold (say, one or two elements), solve the problem directly using a straightforward method and return the solution so obtained. Otherwise, devide the input data into two or more disjoint subsets.

2. Recur: Recursively solve the sub-problems associated with the subsets.

3. Conquer: Take the solutions to the sub-problems and "merge" them into a solution to the original problem.

Merge Two Sorted Arrays:

Merge-Sort

Runtime: Average and Worst-case: O(nlogn), Memory: depends

Quick-Sort

Runtime: Average: O(nlogn)l worst-case: O(n^2); Memory: O(logn)

1. Divide: x -> pivot, sort S

(1) L: Sorting the elements in S less than x;

(2) E: Sorting the elements in S equal to x;

(3) G: Sorting the elements in S greater than x.

2. Recur: Recursively sort sequence L and G

3. Conquer: Put back the elements into S in order by first inserting the elements of L, then those of E, and finally those of G.



Bucket-Sort

Radix-Sort

The radix-sort algorithm sorts a sequence of S of entries with keys that are pares, by applying a table bucket-sort on the sequence twice: first sort using the second component and then using the first component.