Convert recursive merge sort to iterative using stack

I have implemented the merge sort recursively, using linked list, but I am also interested to implement it iteratively using a stack.

This is my recursive implementation:

typedef int element_t;
typedef struct node_s* node_t;

struct node_s {
  element_t data;
  node_t next;
};

typedef struct list_s list_t;
struct list_s {
  node_t first;
  node_t last;
};

list_t* empty_list() {
  list_t* l = malloc(sizeof * l);
  if (!l) return l; 
  l->first = l->last = NULL;
  return l;
}

void list_push_back(element_t elm, list_t *l) {
  node_t cur = create_node(elm, l);
    if (!l->first) {
        l->first = cur;
    }
    else {
        l->last->next = cur;
    }
    l->last = cur;
}

void list_split(list_t *l, list_t *l1, list_t *l2) {
  if (l == NULL || l->next == NULL) {
    l1 = l1->last = NULL;
    if (l) l1 = l1->last = l; //l1->last->next = NULL; is already implied
    l2 = NULL = l2->last = NULL;
  } 
  else {
    node_t slow = l;
    node_t fast = l->next;
    node_t prev_fast2 = fast, prev_fast1 = fast;
    while (fast != NULL) {
      fast = fast->next;
      prev_fast1 = fast;
      if (fast != NULL) {
        slow = slow->next;
        fast = fast->next;
        prev_fast2 = fast;
      }
    }
    l1 = l;
    l1->last = slow;
    l2 = slow->next;
    l2->last = prev_fast2; //assuming length is even
    if (!prev_fast2) //then length is odd
      l2->last = prev_fast1;
    l1->last->next = NULL;
    l2->last->next = NULL;
  }
}

void list_merge(list_t *l, list_t *l1, list_t *l2) {
  if (l1 == NULL) l = l2;  
  else if (l2 == NULL) l = l1;
  else {
    while (l1 != NULL && l2 != NULL) {
      node_t left = l1->first, right = l2->first;
      if (left->data <= right->data) {
        list_push_back(left->data, l);
        l1->first = l1->first->next;
      }
      else {
        list_push_back(right->data, l);
        l2->first = l2->first->next;
      }
    }
    if (l1) {
      l->last->next = l1->first;
      l->last = l1->last;
    }
    if (l2) {
      l->last->next = l2->first;
      l->last = l2->last;
    }
  }
}

list_t* list_merge_sort(list_t *l) {
  if (l->first != NULL && l->first->next != NULL) {
    list_t *l1 = empty_list(), *l2 = empty_list();
    list_split(l, l1, l2);
    list_merge_sort(l1);
    list_merge_sort(l2);
    return list_merge(l1, l2);
  }
  return l;
}

and what follows is what I did with the iterative one... I am still not yet to run it, but is this the right idea of how to go about it? I tried to push only the head because the last gets handled separately and is not helpful to push it.

list_t* list_iter_merge_sort(list_t *l, int size) {
    stack* s = create_stack(size);
    push(s, l->first);
    while (!is_empty(s)) {
      first = pop(s);
      if (first != NULL && first->next != NULL) {
        list_t *l, *l1 = empty_list(), *l2 = empty_list();
        l->first = first;
        list_split(l, l1, l2);
        push(s, l1->first);
        push(s, l2->first);
        l = list_merge(l1, l2);
      }
      else 
        return l;
    }
  }
}

You don't actually need a stack to do an iterative merge sort. Start with the smallest list sizes for partitions, keep merging such partitions pairwise and then repeat with the double size, ...etc.

Here is an implementation where I omitted the list type and only used a struct node -- it saves quite some overhead with creating lists, and setting their first and last pointers during the whole process.

#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node *next;
};
struct node* create_node_before(int data, struct node *next) {
struct node* new = malloc(sizeof *new);
if (!new) exit(1);
new->data = data;
new->next = next;
return new;
}
struct node* create_node(int data) {
return create_node_before(data, NULL);
}
struct node* array_to_list(int a[], int size) {
struct node *first = NULL;
for (int i = size - 1; i >= 0; i--) {
first = create_node_before(a[i], first);
}
return first;
}
void print_list(struct node *first) {
while (first) {
printf("%d ", first->data);
first = first->next;
}
printf("\n");
}
/////////////////////////////////////////////
struct node* cut_and_next(struct node *tail) {
if (!tail) return tail;
struct node *next = tail->next;
tail->next = NULL;
return next;
}
struct node* list_merge_sort(struct node *first) {
if (!first || !first->next) {
return first;
}
struct node *tail, *second, *third, *dummy = create_node_before(0, first);    
for (int size = 1, mergeCount = 2; mergeCount > 1; size *= 2) {
tail = dummy;
first = dummy->next;
mergeCount = 0;
while (first) {
// Get the next two partitions at `size` boundaries:
second = first;
third = first->next;
for (int i = 1; second && i < size; i++) {
second = second->next;
if (third) third = third->next;
if (third) third = third->next;
}
second = cut_and_next(second);
third = cut_and_next(third);
// merge
mergeCount++;
while (first || second) {
if (first && (!second || first->data < second->data)) {
tail = tail->next = first;
first = first->next;
} else {
tail = tail->next = second;
second = second->next;
}
}
first = third;
}
}
return dummy->next;
}
int main(void) { // Demo
int size = 18;
int a[] = {14, 5, 2, 11, 17, 8, 12, 15, 6, 7, 10, 0, 16, 3, 13, 1, 9, 4};
struct node *first = array_to_list(a, size);
printf("Input:\n");
print_list(first);
first = list_merge_sort(first);
printf("Sorted:\n");
print_list(first);
return 0;
}

If you really want the iterative approach to use a top-down algorithm with stack, then maybe go for this:

#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node *next;
};
struct node* create_node_before(int data, struct node *next) {
struct node* new = malloc(sizeof *new);
if (!new) exit(1);
new->data = data;
new->next = next;
return new;
}
struct node* create_node(int data) {
return create_node_before(data, NULL);
}
struct node* array_to_list(int a[], int size) {
struct node *first = NULL;
for (int i = size - 1; i >= 0; i--) {
first = create_node_before(a[i], first);
}
return first;
}
void print_list(struct node *first) {
while (first) {
printf("%d ", first->data);
first = first->next;
}
printf("\n");
}
int is_sorted(struct node *first) {
while (first && first->next) {
if (first->data > first->next->data) return 0; // Not sorted
first = first->next;
}
return 1; // sorted
}
////////////////// STACK //////////////////////////
struct stack_elem {
struct node *elem;
struct stack_elem *next;
};
void push_node(struct stack_elem **top, struct node *elem) {
struct stack_elem *new = malloc(sizeof *elem);
if (!new) exit(1);
new->next = *top;
new->elem = elem;
*top = new;
}
struct node* pop_node(struct stack_elem **top) {
if (!*top) return NULL;
struct node *topnode = (*top)->elem;
struct stack_elem *temp = *top;
*top = temp->next;
free(temp);
return topnode;
}
////////////////////////////////////////////
struct node* split_after(struct node *tail) {
if (!tail) return tail;
struct node *next = tail->next;
tail->next = NULL;
return next;
}
struct node* merge(struct node *first, struct node *second) {
struct node *merged = first;
if (first->data > second->data) {
merged = second;
second = second->next;
} else {
first = first->next;
}
struct node *tail = merged;
while (first && second) {
if (first->data < second->data) {
tail = tail->next = first;
first = first->next;
} else {
tail = tail->next = second;
second = second->next;
}
}
tail->next = first ? first : second;
return merged;
}
struct node* middle(struct node *first) {
// find middle with slow/fast traversal
struct node *slow = first;
struct node *fast = first->next;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
struct node* list_merge_sort_iter(struct node *first) {
struct stack_elem *stack = NULL;
while (1) {
while (!is_sorted(first)) {
// Split off second half and stack it
push_node(&stack, split_after(middle(first)));
}
struct node *second = pop_node(&stack);
while (second && is_sorted(second)) {
first = merge(first, second);
second = pop_node(&stack);
}
// All is sorted? -> exit
if (!second) return first;
push_node(&stack, first); // Save sorted list for later
first = second; // Unsorted list
// Split off second half and stack it
push_node(&stack, split_after(middle(first)));
}
}
int main(void) {
int size = 18;
int a[] = {14, 5, 2, 11, 17, 8, 12, 15, 6, 7, 10, 0, 16, 3, 13, 1, 9, 4};
struct node *first = array_to_list(a, size);
printf("Input:\n");
print_list(first);
first = list_merge_sort_iter(first);
printf("Sorted:\n");
print_list(first);
return 0;
}