sortLinked function

dynamic sortLinked(dynamic list)

Implementation

sortLinked(list) {
  var i, p, q, e, tail, numMerges, pSize, qSize, 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 <= q.z)) {
          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;
}