Simple merge sort

merge_sort.cpp

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <string>

using namespace std;

typedef long long ll;
typedef long double ld;

struct node {
  int value;
  node *next;
};

void push_back(node *&root, int value) {
  if (root)
    push_back(root->next, value);
  else
    root = new node{value, nullptr};
}

void push_front(node *&root, int value) {
  root = new node{value, root};
}

int len(node *root) {
  if (root)
    return len(root->next) + 1;
  else
    return 0;
}

node *split(node *root) {
  int length = len(root);
  node *cur = root;
  for (int i = 0; i < length / 2 - 1; ++i)
    cur = cur->next;
  node *result = cur->next;
  cur->next = nullptr;
  return result;
}

node *merge(node *first, node *second) {
  node dummy{0, nullptr};
  node *cur = &dummy;
  while (first && second) {
    node *best;
    if (first->value < second->value) {
      best = first;
      first = first->next;
    } else {
      best = second;
      second = second->next;
    }
    cur = cur->next = best;
  }
  cur->next = first ? first : second;
  return dummy.next;
}

void sort(node *&list) {
  if (!list || !list->next)
    return;
  node *rest = split(list);
  sort(list);
  sort(rest);
  list = merge(list, rest);
}

int main() {
  node *list = nullptr;
  push_front(list, 1);
  push_front(list, 2);
  push_front(list, 3);
  push_front(list, 4);
  push_front(list, 5);
  push_front(list, 4);
  push_front(list, 5);
  sort(list);
  while (list) {
    cout << list->value << " ";
    list = list->next;
  }
  cout << endl;
  return 0;
}