Algorithms in a Nutshell

Median Sort

Divide and conquer, a common approach in computer science, solves a problem by dividing it into two independent subproblems, each about half the size of the original problem. Consider the Median Sort algorithm ( Figure 4-8) that sorts an array A of n≥1 elements by swapping the median element A[me] with the middle element of A (lines 2–4), creating a left and right half of the array. Median Sort then swaps elements in the left half that are larger than A[mid] with elements in the right half that are smaller or equal to A[mid] (lines 5–8). This subdivides the original array into two distinct subarrays of about half the size that each need to be sorted. Then Median Sort is recursively applied on each subarray (lines 9–10).

Figure 4-8. Median Sort fact sheet

A full example of Median Sort in action is shown in Figure 4-9, in which each row corresponds to a recursive invocation of the algorithm. At each step, there are twice as many problems to solve, but each problem size has been cut in about half. Since the subproblems are independent of each other, the final sorted result is produced once the recursion ends.

Figure 4-9. Median Sort in action on small array

The initial unsorted array is shown in the line labeled 1a, and the selected median element, A[me], is identified by a gray ...