Внешняя сортировка

Введем понятие последовательности:

До­пу­стим, у нас есть два от­сор­ти­ро­ван­ных мас­си­ва A и B раз­ме­ра­ми и со­от­вет­ствен­но, и мы хо­тим объ­еди­нить их эле­мен­ты в один боль­шой от­сор­ти­ро­ван­ный мас­сив C раз­ме­ром . Для это­го мож­но при­ме­нить про­це­ду­ру слия­ния, суть ко­то­рой за­клю­ча­ет­ся в по­вто­ряю­щем­ся «от­де­ле­нии» эле­мен­та, наи­мень­ше­го из двух имею­щих­ся в на­ча­лах ис­ход­ных мас­си­вов, и при­со­еди­не­нии это­го эле­мен­та к кон­цу ре­зуль­ти­рую­ще­го мас­си­ва. Эле­мен­ты мы пе­ре­но­сим до тех пор, по­ка один из ис­ход­ных мас­си­вов не за­кон­чит­ся. По­сле это­го остав­ший­ся «хвост» од­но­го из вход­ных мас­си­вов до­пи­сы­ва­ет­ся в ко­нец ре­зуль­ти­рую­ще­го мас­си­ва. При­мер ра­бо­ты про­це­ду­ры по­ка­зан на ри­сун­ке:

Ес­те­ствен­ная сор­ти­ров­ка

До сих пор мы рас­смат­ри­ва­ли ал­го­рит­мы сор­ти­ров­ки, ко­то­рые ни­как не учи­ты­ва­ют то, что дан­ные (или их часть) мо­гут быть уже от­сор­ти­ро­ва­ны. Для ал­го­рит­ма сор­ти­ров­ки слия­ни­ем есть очень про­стая и эф­фек­тив­ная мо­дифи­ка­ция, ко­то­рая на­зы­ва­ет­ся «ес­те­ствен­ная сор­ти­ров­ка» («Natural Sort»). Суть её в том, что нуж­но об­ра­зо­вы­вать це­поч­ки, и про­из­во­дить их слия­ние не в за­ра­нее опре­де­лён­ном и фик­си­ро­ван­ном по­ряд­ке, а ана­ли­зи­ро­вать имею­щие­ся в мас­си­ве дан­ные. Ал­го­ритм сле­дую­щий:

1. раз­бить мас­сив на це­поч­ки уже от­сор­ти­ро­ван­ных эле­мен­тов (в худ­шем слу­чае, ко­гда эле­мен­ты в мас­си­ве идут по убы­ва­нию, все це­поч­ки бу­дут со­сто­ять из од­но­го эле­мен­та);

2. про­из­ве­сти слия­ние це­по­чек ме­то­дом сдваи­ва­ния.

При­мер ра­бо­ты это­го ал­го­рит­ма по­ка­зан на ри­сун­ке: