Use order statistics to select the median of an array in linear time without sorting.

select.d

import std.stdio;

auto swap(T)(ref T a, ref T b) {
    T tmp = a;
    a = b;
    b = tmp;
}

auto part(T)(T[] array, int low, int high) {
    auto size = low-1;
    auto pivot = array[high-1];
    foreach (i; low .. high) {
        if (array[i] < pivot) {
            ++size;
            swap(array[i], array[size]);
        }
    }
    swap(array[size+1], array[high-1]);
    return size + 1;
}

auto select(T)(T[] array, int low, int high, int k) {
    while (true) {
        auto pivotIndex = part(array, low, high);
        auto len = pivotIndex - low; 
        if (k == len) {
            return array[pivotIndex];
        } else if (k < len) {
            high = pivotIndex;
        } else {
            k -= len;
            low = pivotIndex + 1;
        }
    }
}

void main() {
    auto array = [5,1,6,2,7,4,8,3,10];
    writeln(select(array, 0, array.length, array.length/2));
}