sortLinked function

dynamic sortLinked(dynamic list)

Implementation

sortLinked(list) {
  late int i;
  Node? p;
  Node? q;
  Node? e;
  Node? tail;
  int numMerges = 0;
  late int pSize;
  late int qSize;
  int inSize = 1;

  do {
    p = list;
    list = null;
    tail = null;
    numMerges = 0;

    while (p != null) {
      numMerges++;
      q = p;
      pSize = 0;
      for (i = 0; i < inSize; i++) {
        pSize++;
        q = q?.nextZ;
        if (q == null) break;
      }

      qSize = inSize;

      while (pSize > 0 || (qSize > 0 && q != null)) {
        if (pSize != 0 && (qSize == 0 || q == null || (p?.z ?? 0) <= (q.z ?? 0))) {
          e = p;
          p = p?.nextZ;
          pSize--;
        } else {
          e = q;
          q = q?.nextZ;
          qSize--;
        }

        if (tail != null) {
          tail.nextZ = e;
        } else {
          list = e;
        }

        e?.prevZ = tail;
        tail = e;
      }

      p = q;
    }

    tail?.nextZ = null;
    inSize *= 2;
  } while (numMerges > 1);

  return list;
}