# 2014秋マージソート

class Cell:
    def __init__(self, value):
        self.value = value
        self.next = None

def divide(list_head):
    # 図5のアルゴリズムを忠実に再現
    a = list_head
    b = a.next
    if b is not None:
        b = b.next
    
    # 【ア】の条件: bが終端に達するまで
    while b is not None:  
        a = a.next
        b = b.next
        if b is not None:
            # 【イ】の部分: bをもう一歩進める
            b = b.next
            
    p = a.next
    # 【ウ】の部分: 前半のリストの終端をNULL(None)にする
    a.next = None
    return p

def merge(a, b):
    # 図7のアルゴリズムを忠実に再現
    # ダミーセルの用意
    head = Cell(None)
    p = head
    
    # 【エ】の条件: aがNULLでない間
    while a is not None and b is not None:
        if a.value <= b.value:
            p.next = a
            p = a
            a = a.next
        else:
            p.next = b
            p = b
            b = b.next
            
    # 【オ】の条件: aがNULLになったか（bが残っているか）
    if a is None:
        p.next = b
    else:
        p.next = a
        
    # 【カ】戻り値: ダミーの次のセル（実際の先頭）を返す
    return head.next

def merge_sort(list_head):
    # 図2の再帰アルゴリズム
    # (1) 要素数が1以下の場合はそのまま返す
    if list_head is None or list_head.next is None:
        return list_head
    
    # (2) リストを分割
    second_half = divide(list_head)
    
    # (3) 再帰的に呼び出し
    first_half_sorted = merge_sort(list_head)
    second_half_sorted = merge_sort(second_half)
    
    # (4) 併合
    return merge(first_half_sorted, second_half_sorted)

# --- 動作確認用の補助関数 ---
def create_linked_list(arr):
    if not arr: return None
    head = Cell(arr[0])
    current = head
    for val in arr[1:]:
        current.next = Cell(val)
        current = current.next
    return head

def print_list(head):
    vals = []
    while head:
        vals.append(str(head.value))
        head = head.next
    print(" -> ".join(vals))

# テスト実行
data = [6, 4, 3, 8, 7, 2, 1, 5]
root = create_linked_list(data)
print("整列前:")
print_list(root)

sorted_root = merge_sort(root)
print("整列後:")
print_list(sorted_root)