#!/usr/bin/env python
# coding: utf
'''
Сортировка файла методом слияния.
Хранение промежуточных результатов в двух файлах
'''

import os, pickle

def joinsort(F1):
    '''Слияние двух файлов, состоящих из последовательностей упорядоченных строк,
    не менее одной строки в каждой. Результат — два новых файла.
    Первый содержит объеденённые попарно упорядоченные чётные последовательности
    исходных файлов, второй — нечётные. После чего исходные файлы заменяются новыми.
    Процесс повторяется, пока второй файл не окажется пустым'''

    F = F1, F1+"2", F1+"A", F1+"B"
    # Для начала сольём исходный файл с пустым
    open(F[1],"w").close()
    n = -1
    while n:
        f = open(F[0],"r"), open(F[1],"r"), open(F[2], "w"), open(F[3],"w")
        s, n = [f[0].readline(), f[1].readline(), ""], 0
        while s[0] or s[1]:
            # Не закончилась ли последовательность?
            if s[2] > max(s[1],s[0]):
                s[2], n = "", n+1
            # Строка из какого файла меньшая, но непустая?
            k = s[1] and (not s[0] or s[0] >= s[1] >= s[2]) and 1 or 0
            f[2+n%2].write(s[k])
            s[2], s[k] = s[k], f[k].readline()
        os.rename(F[2], F[0]); os.rename(F[3], F[1])
    os.remove(F[1])

if __name__=="__main__":
    joinsort("file.data")