15.1.2. Finding the Median

The median is the value such that exactly half the values in the array are bigger and half are smaller.

The median is a statistical measure that represents the middle value in a data set when it is arranged in ascending order. If the number of observations is odd, the median is the middle number. If it is even, the median is the average of the two middle numbers. For example, in the array [1, 3, 3, 6, 7, 8, 9], the median is 6, as it is the fourth element in an arrangement of seven numbers. In the case of an even number of elements, say [1, 2, 3, 4], the median would be (2 + 3) / 2 = 2.5.

Imagine a class of students lined up by height. The student standing in the middle of the line is the median height, meaning half the class is taller, and half is shorter. This can help the teacher understand the average height of the class, similar to how the median helps in data analysis.

We move everything which is smaller than the median to the left half and everything larger to the right half.

Once we find the median, we can rearrange the elements in the array such that all numbers less than the median move to its left, and all numbers greater than the median shift to its right. This is an important step in sorting the array without needing additional storage, as we can manage the sort in a single pass by organizing the array around the median.

Think of the median as a separation line on a football field. Players on the left side of the line are shorter than the median height, and those on the right are taller. As the coach organizes the team for practice, he instructs the players to stand on their respective sides according to their heights, which helps him visually assess the team's overall height distribution.

The claim is that we can do this shifting in linear time, allowing for efficient sorting.

The process of shifting elements around the median can be done in linear time because it only requires one pass through the array to compare each element with the median and shift it accordingly. This means if the array has 'n' elements, we can achieve this rearrangement in O(n) time complexity. Such efficiency is crucial in algorithm design, as faster algorithms handle larger data sets more effectively.

Consider a librarian organizing books on a shelf. Instead of removing and then replacing each book, the librarian quickly glances at each book one by one, moving them to the correct side of the shelf in one continuous action. This saves time and allows her to organize hundreds of books quickly.

After shifting, we can recursively sort the left and right partitions without the need for merging.

By determining the positions of the left and right partitions around the median, we can recursively apply the same process to sort those sub-arrays. The absence of merging makes the process more efficient since each element is already in its relative position concerning the median. This recursive approach leads to an efficient sort similar to merge sort, ultimately resulting in a sorted array without additional storage overhead.

Imagine building a pyramid using blocks. First, you create a layer (the median) that perfectly divides your blocks into two groups: larger blocks on one side, smaller blocks on the other. You then focus on stacking each group individually until the entire pyramid is complete. This method is simpler than sorting the whole pile all at once.

--