Алгоритм соединения слиянием сортированных списков

Алгоритм соединения слиянием сортированных списков (merge join, sort merge join, sort-merge join) — разновидность алгоритма соединения.

Алгоритм получает на вход две таблицы и условие соединения. Результатом его работы является таблица с результатами соединения.

Входные таблицы должны быть отсортированы по столбцам, участвующим в условии соединения. Соединение осуществляется за одно сканирование (проход по) каждой из входных таблиц. То есть одна и та же строка считывается только один раз, что даёт преимущество перед соединением вложенными циклами.

Простой пример на псевдокоде:

 //нужно соединить Таблицу 1 и Таблицу 2  
 //по условию: Таблица1.Колонка1 = Таблица2.Колонка2
 //Для упрощения примера будем считать, что значения в Колонке2 уникальны

 Таблица1.Сортировать(Колонка1);
 Таблица2.Сортировать(Колонка2);
 Таблица1.ВстатьНаПервуюЗапись;
 Таблица2.ВстатьНаПервуюЗапись;
 Пока Таблица1.НеПоследняяЗапись и Таблица2.НеПоследняяЗапись
 {
     Если Таблица1.Колонка1 < Таблица2.Колонка2
     {
         Таблица1.ПерейтиКСледующейЗаписи;
     }  
     Иначе Если Таблица1.Колонка1 = Таблица2.Колонка2
     {
         Вывести (Таблица1.ТекущаяЗапись, Таблица2.ТекущаяЗапись);
         Таблица1.ПерейтиКСледующейЗаписи;
         Таблица2.ПерейтиКСледующейЗаписи;
     }
     Иначе Если Таблица1.Колонка1 > Таблица2.Колонка2
     {
         Таблица2.ПерейтиКСледующейЗаписи;
     }			
 }