Skip to content
TheChatArchiveThe Chat Archive
Claudeclaude-2.1· AnthropicHugging Face Arena Human Preference 55K

What is the most efficient algorithm for finding the median of an unsorted list of…

From a Chatbot Arena battleThe same person sent this prompt to two anonymous models at once. Compare it with gpt-4-0314’s answer.
  1. User

    What is the most efficient algorithm for finding the median of an unsorted list of numbers?

  2. Claude Assistant

    Here are a few of the most efficient algorithms for finding the median of an unsorted list of numbers:

    1. Quickselect
    • Uses the quicksort partitioning approach to find the median in linear time on average. Quickselect picks a pivot, partitions the array around the pivot in linear time, and recurses on one side of the partition depending on if the pivot is the median. Worst case is O(n^2) but average is O(n).
    1. Heap Selection
    • Build a max-heap and min-heap in linear time by heapifying the array. Find the medians from the heaps in constant time. Overall runtime is O(n) worst case. Requires more space for the heaps.
    1. Insertion Sort/Selection Algorithm Hybrid
    • Perform insertion sort on first 5 elements to find median. Then for next elements, use selection algorithm to select which elements go in low vs high side of sorted list to maintain median. Overall runtime is O(n) on average and O(n^2) worst case.
    1. Stochastic Selection
    • Select random pivots and partition around them. Recurse until partition with median is found. Expected linear runtime similar to quickselect.

    Of these, quickselect and the heap selection algorithm are generally the most efficient in practice as they provide O(n) runtime on average. The hybrid algorithm is also competitive if the input list is partially sorted.

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.