アルゴリズムクイックリファレンス：中央値ソート

median_sort.py

def sort(target):
    median_sort(target, 0, len(target) - 1)
    return target


def median_sort(target, left, right):
    if left < right:
        # find median
        mid_point = (left + right) / 2
        min_value = target[left]
        max_value = target[left]
        
        index = left
        while index <= right:
            min_value = min(min_value, target[index])
            max_value = max(max_value, target[index])
            index += 1
            
        median_value = (max_value + min_value) / 2
        median_point = target.index(median_value)
        
        # swap median to mid_point
        swap(target, mid_point, median_point)
        
        # partition left to right
        left_point = left
        while left_point <= mid_point - 1:
            if target[left_point] > median_value:
                right_point = mid_point + 1
                while right_point <= right:
                    if target[left_point] > target[right_point] and target[right_point] < median_value:
                        swap(target, target.index(target[left_point]), target.index(target[right_point]))
                        break
                    right_point += 1
            left_point += 1

        # swap left part
        median_sort(target, left, mid_point - 1)
        
        # swap right part
        median_sort(target, mid_point + 1, right)


def swap(target, a, b):
    target[b], target[a] = target[a], target[b]
    return target