The Sort-Merge Join is an example of a join algorithm and is used in the implementation of a relational database management system.

The basic problem of a join algorithm is to find, for each distinct value of the join attribute, the set of tuples in each relation which display that value. The key idea of the Sort-merge algorithm is to first sort the relations by the join attribute, so that interleaved linear scans will encounter these sets at the same time.

For simplicity, the algorithm is described in the case of an inner join of two relations on a single attribute. Generalization to other join types, more relations and more keys is straightforward.

 function sortMerge(relation left, relation right, attribute a)
     var relation output
     var list left_sorted := sort(left, a)
     var list right_sorted := sort(right, a)
     var left_key
     var right_key
     var set left_subset
     var set right_subset
     advance(left_subset, left_sorted, left_key, a)
     advance(right_subset, right_sorted, right_key, a)
     while not empty(left_sorted) and not empty(right_sorted)
         if left_key = right_key
             add cross product of left_subset and right_subset to output
             advance(left_subset, left_sorted, left_key, a)
             advance(right_subset, right_sorted, right_key, a)
         else if left_key < right_key
            advance(left_subset, left_sorted, lef_key, a)
         else // right_key < left_key
            advance(right_subset, right_sorted, right_key, a)
     return output
 function advance(key, subset, sorted, a)
     key = sorted[1].a
     subset = emptySet
     while not empty(sorted) and sorted[1].a = key
         insert(subset, sorted[1])
         remove first element from sorted