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_front(node *&root, int value) {
  root = new node{value, root};
}

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

// Rearrange segment [first, end) by merging segments [first, second) and [second, end) and return pointer to the new pointer to the end.
node **merge(node *&first, node *second, node *end) {
  node dummy{0, nullptr};
  node *cur = &dummy;
  node *iter1 = first, *iter2 = second;
  while (iter1 != second && iter2 != end) {
    node *best;
    if (iter1->value <= iter2->value) {
      best = iter1;
      iter1 = iter1->next;
    } else {
      best = iter2;
      iter2 = iter2->next;
    }
    cur = cur->next = best;
  }
  
  cur->next = (iter1 == second) ? iter2 : iter1;
  while (cur->next != second && cur->next != end)
    cur = cur->next;
  cur->next = end;

  first = dummy.next;
  return &(cur->next);
}

void sort(node *&list) {
  if (!list || !list->next)
    return;
  int length = len(list);
  for (int seglen = 2; seglen <= length * 2; seglen *= 2) {
    node **start, *mid, **end = &list;
    while (*end != nullptr) {
      start = end;
      for (int i = 0; i < seglen; ++i) {
        if (i == seglen / 2)
          mid = *end;
        if (*end == nullptr)
          break;
        end = &((*end)->next);
      }
      end = merge(*start, mid, *end);
    }
  }
}

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);
  node *cur = list;
  while (cur) {
    cout << cur->value << " ";
    cur = cur->next;
  }
  cout << endl;
  sort(list);
  while (list) {
    cout << list->value << " ";
    list = list->next;
  }
  cout << endl;
  return 0;
}