import heapq
import os
import tempfile
from typing import Iterator, List, Callable
import more_itertools

TLine = bytes


def compare_key(line):
    i = line.index(b'.')
    number = int(line[:i])
    string = line[i + 2:]
    return string, number


class File:
    """Представляет файл со строками"""

    def __init__(self, filename: str) -> None:
        self.filename = filename

    def write_lines(self, lines: Iterator[TLine]) -> None:
        with open(self.filename, 'wb') as f:
            for line in lines:
                f.write(line)
                f.write(b'\n')

    def read_lines(self) -> Iterator[TLine]:
        with open(self.filename, 'rb') as f:
            for line in f:
                yield line.rstrip(b'\n')


class Sorter:
    """Сервис, реализующий внешнюю сортировку файла"""

    def __init__(self, chunk_size: int = 10_000, compare_key_func: Callable = None) -> None:
        # количество строк, одновременно загружаемых в память для сортировки
        self.chunk_size = chunk_size
        # строки в файле сортируются по значению, возвращенному этой функцией
        self.compare_key_func = compare_key_func or (lambda line: line)

    def sort_file(self, input_file: File, output_file: File) -> None:
        """Сортирует строки исходного файла и записывает в выходной файл"""

        with tempfile.TemporaryDirectory() as temp_dir:
            input_lines = input_file.read_lines()
            chunks_files = self._save_chunks(input_lines, temp_dir=temp_dir)
            sorted_lines = self._merge_chunks(chunks_files)
            output_file.write_lines(sorted_lines)

    def _save_chunks(self, lines: Iterator[TLine], temp_dir: str) -> Iterator[File]:
        """Разбивает поток строк на отсортированные чанки"""

        chunks = more_itertools.ichunked(lines, self.chunk_size)
        for chunk_index, chunk_lines in enumerate(chunks):
            sorted_lines = sorted(chunk_lines, key=self.compare_key_func)
            filename = os.path.join(temp_dir, f'{chunk_index}.txt')
            chunk_file = File(filename)
            chunk_file.write_lines(sorted_lines)
            yield chunk_file

    def _merge_chunks(self, files: List[File]) -> Iterator[TLine]:
        """Объединяет отсортированные файлы-чанки в поток отсортированных строк"""

        iterators = [file.read_lines() for file in files]
        return heapq.merge(*iterators, key=self.compare_key_func)


Sorter().sort_file(input_file=File(...), output_file=File(...))

class LineGenerator:
    """Сервис для генерации строк в соответствии с заданием"""

    # диапазон числа, стоящего в начале строки
    NUMBER_RANGE = (0, 10_000)
    # диапазон длины текстовой части строки
    LINE_LENGTH_RANGE = (20, 200)
    # допустимые символы в текстовой части строки
    LETTERS = 'abcdefghijklmnopqrstuvwxyz'
    # количество предопределенных вариантов текстовой части строки
    # нам нужны предопределенные варианты, чтобы обеспечить повторение некоторых строк в файле (по условию)
    DISTINCT_STRING_COUNT = 1000

    def generate_line(self) -> TLine:
        number = random.randint(*self.NUMBER_RANGE)
        string = random.choice(self._strings)
        return f'{number}. {string}'.encode()

    def generate_many_lines(self, count) -> Iterator[TLine]:
        return (self.generate_line() for _ in range(count))

    @cached_property
    def _strings(self) -> List[str]:
        strings = []
        for _ in range(self.DISTINCT_STRING_COUNT):
            string_len = random.randint(*self.LINE_LENGTH_RANGE)
            string = ''.join(random.choice(self.LETTERS) for _ in range(string_len))
            strings.append(string)
        return strings


lines = LineGenerator().generate_many_lines(100_000_000)
File(...).write_lines(lines)