Przez serię w pliku będę miał na myśli uporządkowane linie - np. dla
a
b
c
x
a
h
y
jedną serią będzie a b c x, natomiast drugą a h y.
Najpierw dzielisz plik z tekstem na dwa tymczasowe pliki w następujący sposób (sortowanie rosnące):
- pobierasz z pliku pierwszą linię i zapisujesz ją do do pierwszego pliku
- dopóki nie natrafisz na koniec pliku wykonaj:
- pobierz linię z pliku
- jeżeli jej wartość jest większa od poprzedniej, zapisujesz ją w tym samym pliku, co poprzednią
- w przeciwnym zmieniasz plik docelowy na ten drugi, do którego nie zapisałeś poprzedniej linii.
Jak masz już podzielony plik na dwie części, przechodzimy do scalania. To, co trzeba zrozumieć i zwrócić uwagę to fakt, że jak wczytujesz kolejne linie z plików pomocniczych, to rozpoczynasz czytanie nowej serii dopiero jak skończyłeś czytać aktualnie sortowanie serie z obu plików (przynajmniej mi zrozumienie tego przysporzyło sporo kłopotów, może tobie pójdzie łatwiej):
- pobierz z obu plików pomocniczych ich pierwsze linie;
- dopóki oba pliki nie będą puste:
- dopóki aktualnie sortowane serie w pliku nie są przeczytane:
- wybierz linię o mniejszej wartości i wpisz ją do pliku docelowego;
- z pliku, z którego pochodziła mniejsza linia pobierz kolejną linię (o ile jeszcze jakaś została - jeżeli nie przepisujesz do pliku docelowego resztę serii z drugiego pliku i zaczynasz wracasz do głównej pętli);
- pobierz z obu plików nowe linie
Obie te fazy powtarzasz tak długo, aż podczas fazy podziału cała zawartość pliku źródłowego została przepisana tylko do jednego pliku pomocniczego - to znaczy, że masz tylko jedną serię i plik jest posortowany. Co prawda warunek nie jest do końca zogdny z teoretycznimi założeniami algorytmu, ale co działa (y) .
Może przykład pozwoli ci lepiej zrozumieć:
Plik: (N =8) 44 55 | 12 42 94 | 18 | 06 67 (4 serie różnej długości)
Serie są dystrybuowane naprzemiennie na 2 taśmy:
1. faza:
t1: 44 55 | 18
t2: 12 42 94 | 06 67
t3: 12 42 44 55 94 | 06 18 67 (2 serie)
2. faza:
t1: 12 42 44 55 94
t2: 06 18 67
t3: 06 12 18 42 44 55 67 94 (1 seria, plik posortowany)
https://github.com/mmichal10/natural-merge - moja implementacja w c - nie brakuje tu pewnie jakichś złych praktyk, wycieków pamięci itp. Miałem trochę inne rekordy to posortowania, ale może kod ci w czymś pomoże. Ciebie powinny zainteresować funkcje split() i merge() z pliku fileManager.c. W moim kodzie jest zapimplementowany mechanim stronnicowania, co może utrudnić jego zrozumienie, ale wydaje mi się, że jeżeli zignorujesz zmienne z 'offset' w nazwie, a putInBuffer i getRecord potraktujesz jako zwykłe pisanie i czytanie z pliku, to sporo ułatwi.