[参加者募集/ Python]君ならどう書く？ -merge sort-

本家 LLRing 風にちょっとした問題で遊んでみようと思います。Python 以外の言語の参加もお待ちしています。お題は↓

任意の大きさの配列 X に対してマージソートを行い、要素を昇順に並べ替えるコード

わたしの場合はこんな感じになりました。

def prepare_divide( unsorted_list ):
    length = len( unsorted_list )
    intermediate = [ unsorted_list[: length/2 ], unsorted_list[ length/2 :]]
    intermediate.sort()
    
    return intermediate


def divide( unsorted_list ):
    intermediate = prepare_divide( unsorted_list )
    divided_list = []
    for part in intermediate :
        max_length = len( part )
        while max_length > 1:
            divided_list += prepare_divide( part )
            
            max_length    = max( [ len(x) for x in divided_list ] )
            part = divided_list.pop( [ len(x) for x in divided_list ].index( max_length ) )
        else:
            divided_list.append( part )
        
    return divided_list


def merge( merged_list, sorted_list ):
    # Two list objects are required.
    # Both are must be sorted.
    
    probable_merged = []
    x = 0; y = 0
    try:
        x = merged_list.pop(0)
        y = sorted_list.pop(0)
    except:
        pass
    
    # To break Loop, chatching exception IndexError occured by list.pop(0)
    # Because lacking elements of lists, do Not write "while( list1 or list2 )"
    while 1:
        try:
            if( x < y ):
                probable_merged .append( x )
                x = merged_list.pop(0)
            elif( y < x ):
                probable_merged .append( y )
                y = sorted_list.pop(0)
            elif( ( x == None ) or ( y == None ) ):
                notNone = lambda i, j: i or j
                probable_merged .append( notNone( x, y ) )
        except IndexError:
            # When IndexError is raised, one of lists became empty.
            # Then appending the other into probable_merged
            if x in probable_merged:
                if not( y in probable_merged ):
                    probable_merged.append(y)
            elif   not( x in probable_merged ):
                probable_merged.append(x)
            probable_merged = probable_merged + merged_list + sorted_list
            break
        except AttributeError:
            break
    
    return probable_merged


def merge_sort( unsorted_list ):
    if type( unsorted_list ) != type( [] ) :
        import sys
        print "Argument must be List."
        sys.exit()
    
    divided_list = divide( unsorted_list )
    merged_list  = divided_list.pop(0)
    sorted_list  = []
    
    while len(divided_list) > 0:
        sorted_list = divided_list.pop(0)
        merged_list = merge( merged_list, sorted_list )
    return merged_list

↑が見難い場合はこちら。
再帰を使わずに書いて見ました。merge() がなんか汚いです( ´･ω･`)

prepare_divide() と divide() で配列を分割。

merge() で2つのリストを統合。やっていることは単純で、2つの配列の中から一番小さな値から順に取り出して新しい配列に並べているだけ。例外を補足した後にごちゃごちゃやっているのは、要素が重複しないようにするため。

最後の merge_sort() はインターフェイス関数。引数のチェックと他の関数 divide() と merge() への引数パスとソート済みリストの出力を担当してます。

Python には要素が重複しないオブジェクトとして set オブジェクトがあるけど、これは unordered collection なのでソートには不向き。残る方法は、とりあえず全部突っ込んでから重複した要素を取り除くか、最初から要素が重複しないようにすることだけど、後者の方が簡単だと思って上のように実装しました。

三項演算子と do-while があったらもっと綺麗になりそうだなと思いつつ書き書き。たった一文字のTYPOに気付けずにデバッグに4時間半かかりましたとさ。最強のバグは TYPO かもしれない ＿|￣|○il|!

2006.09.18
バグ＆コメントのTYPO修正。
型チェックのつもりのコードが同値検査になってたよ＿|￣|○il|!