## DropSort algorithm
# O(n log n) -- good constants for data with some ordering;
#               bad for randomly-distributed data
#
# (c)2009 Jeremiah Kent
# ibiwan@gmail.com
#
# inspired by David Morgan-Mar's Dropsort algorithm,
# found at http://www.dangermouse.net/esoteric/dropsort.html
#
# October 2010, Style enhancements by Michiel Overtoom, motoom@xs4all.nl


class Stats(object):
    "Counts events and displays statistics"

    def __init__(self):
        self.comparisons = self.copies = self.merges = 0

    def comparison(self):
        self.comparisons += 1

    def copy(self):
        self.copies += 1

    def merge(self):
        self.merges += 1

    def __str__(self):
        return "%d comparisons, %d copies, %d merges" % (self.comparisons,
                self.copies, self.merges)


def merge(srca, srcb, stats):
    stats.merge()
    result = []
    a = b = 0
    while a < len(srca) and b < len(srcb):
        stats.comparison()
        if srca[a] <= srcb[b]:
            stats.copy()
            result.append(srca[a])
            a += 1
        else:
            stats.copy()
            result.append(srcb[b])
            b += 1
    stats.copy()
    result.extend(srca[a:]) # leftovers
    result.extend(srcb[b:])
    return result


def dropsort(lst, stats):
    if len(lst) < 2:
        return lst
    up = []
    dn = []
    prev = None
    for i in lst:
        stats.comparison()
        if not prev or i >= prev:
            stats.copy()
            up.append(i)
            prev = i
        else:
            stats.copy()
            dn.insert(0, i)
    return merge(up, dropsort(dn, stats), stats)


def mergesort(lst, stats):
    """Standard mergesort"""
    if len(lst) < 2:
        return lst
    mid = len(lst) / 2
    return merge(mergesort(lst[:mid], stats),
           mergesort(lst[mid:], stats), stats)


def hybrid(lst, stats, stage=0):
    """Hybrid sort: Use dropsort for the first two recursion levels in case
    there's already ordered data, then merge remainder."""
    if len(lst) < 2:
        return lst
    if stage > 1:
        return mergesort(lst, stats)
    up = []
    dn = []
    prev = None
    for i in lst:
        stats.comparison()
        if not prev or i >= prev:
            stats.copy()
            up.append(i)
            prev = i
        else:
            stats.copy()
            dn.insert(0, i)
    return merge(up, hybrid(dn, stats, stage + 1), stats)


def printsort(lst, name=None):
    """Print a sorted list, indented. The list is assumed to have
    floats in in range [0, 1)"""
    if name:
        print name
    for i in lst:
        print " " * int(i * 80), i
    print

if __name__ == "__main__":
    # Tests all three sorting methods.
    for method in (mergesort, dropsort, hybrid):
        st = Stats()
        a = [1, 3, 5, 6, 2, 10, 7, 8, 4, 9]
        print method.__name__
        print method(a, st)
        print st, "\n"