merge.c

#include <stdio.h>
#include <stdlib.h>

struct tree {
     int          value;
     struct tree *left;
     struct tree *right;
};

struct stack {
     int           state;
     struct tree  *current;
     struct stack *next;
};

void create(struct stack **stack)
{
     *stack = NULL;
}

void push(int state, struct tree *tree, struct stack **stack)
{
     struct stack *new = malloc(sizeof (struct stack));
     new->state   = state;
     new->current = tree;
     new->next    = *stack;
     *stack       = new;
}

int pop(int *state, struct tree **tree, struct stack **stack)
{
     struct stack *old = *stack;
     if (!old)  return 0;
     if (state) *state = old->state;
     if (tree)  *tree  = old->current;
     
     *stack = old->next;
     free(old);
     return 1;
}

void make_tree(struct tree *nodes, int bound)
{
     int twice = 2 * bound;
     
     for (int i = 1; i < bound; i++) {
          nodes[i].left  = &nodes[2*i];
          nodes[i].right = &nodes[2*i + 1];
     }
     
     for (int i = bound; i < twice; i++) {
          nodes[i].left  = NULL;
          nodes[i].right = NULL;
     }
}

void fill_tree(struct tree *tree, int start, int step)
{
     int           state;
     struct stack *stack;
     
     create(&stack);
     push(0, tree, &stack);
     
     while (pop(&state, &tree, &stack))
          if (state) {
               tree->value  = start;
               start       += step;
          }
          else if (tree) {
               push(0, tree->right, &stack);
               push(1, tree       , &stack);
               push(0, tree->left , &stack);
          }
}

void step(struct stack *stack)
{
     while (pop(&stack->state, &stack->current, &stack->next))
          if (stack->state)
               return;
          else if (stack->current) {
               push(0, stack->current->right, &stack->next);
               push(1, stack->current       , &stack->next);
               push(0, stack->current->left , &stack->next);
          }
}

void start(struct tree *tree, struct stack *stack)
{
     create(&stack->next);
     push(0, tree, &stack->next);
     step(stack);
}

void merge(struct tree *ltree, struct tree *rtree)
{
     struct stack lstack;
     struct stack rstack;
     
     start(ltree, &lstack);
     start(rtree, &rstack);
     
     while (lstack.state && rstack.state)
          if (lstack.current->value <= rstack.current->value) {
               printf("%d ", lstack.current->value);
               step(&lstack);
          }
          else {
               printf("%d ", rstack.current->value);
               step(&rstack);
          }
     
     while (lstack.state) {
          printf("%d ", lstack.current->value);
          step(&lstack);
     }
     
     while (rstack.state) {
          printf("%d ", rstack.current->value);
          step(&rstack);
     }
     
     printf("\n");
}

int main()
{
     struct tree left[64];
     struct tree right[64];
     
     make_tree(left, 32);
     make_tree(right, 32);
     
     fill_tree(&left[1], 2, 2);
     fill_tree(&right[1], 3, 2);
     
     merge(&left[1], &right[1]);
}

merge.sml

datatype 'a tree = Empty | Tree of 'a tree * 'a * 'a tree
datatype 'a step = One of 'a | Many of 'a tree

fun step nil = NONE
  | step (One x :: ss) = SOME (x, ss)
  | step (Many Empty :: ss) = step ss
  | step (Many (Tree (a,x,b)) :: ss) = step (Many b :: One x :: Many a :: ss)

fun one (xs, NONE) = xs
  | one (xs, SOME (x, ys)) = one (x :: xs, step ys)

fun two (xs, ys, NONE) = one (xs, ys)
  | two (xs, NONE, zs) = one (xs, zs)
  | two (xs, yys as SOME (y, ys), zzs as SOME (z, zs)) =
    if y <= z then
      two (z :: xs, yys, step zs)
    else
      two (y :: xs, step ys, zzs)

fun start xs = step (Many xs :: nil)
fun merge (xs, ys) = two (nil, start xs, start ys)