left_sorted, left_key, a) advance(right_subset, right_sorted, right_key, a) else if left_key < right_key advance(left_subset, left_sorted, left_key, a) else // left_key > right_key advance(right_subset, right_sorted, right_key, a) return output // Remove tuples from sorted to subset until the sorted[1].a value changes function advance(subset out, sorted inout, key out, a in) key := sorted[1].a subset := emptySet while not empty(sorted) and sorted[1].a = key insert sorted[1] into subset remove sorted[1] Simple C# implementation Note that this implementation assumes the join attributes are unique, i.e., there is no need to output multiple tuples for a given value of the key. public class MergeJoin { // Assume that left and right are already sorted public static Relation Merge(Relation left, Relation right) { Relation output = new Relation(); while (!left.IsPastEnd() && !right.IsPastEnd()) { if (left.Key == right.Key) { output.Add(left.Key); left.Advance(); right.Advance(); } else if (left.Key < right.Key) left.Advance(); else // if (left.Key > right.Key) right.Advance(); } return output; } } public class Relation { private List<int> list; public const int ENDPOS = -1; public int position = 0; public int Position => position; public int Key => list[position]; public bool Advance() { if (position == list.Count - 1 || position == ENDPOS) { position = ENDPOS; return false; } position++; return true; } public void Add(int key) { list.Add(key); } public bool IsPastEnd() { return position == ENDPOS; } public void Print() { foreach (int key in list) Console.WriteLine(key); } public Relation(List<int> list) { this.list = list; } public Relation() { this.list = new List<int>(); } } See also Hash join Nested loop join References External links C# Implementations of Various Join Algorithms Join algorithms Articles with example pseudocode Articles with example C Sharp code