Tim Sort — VisualAlgorithms Docs

How it works

Hybrid of merge sort and insertion sort. Finds natural runs, extends them, and merges with a sophisticated merge strategy. Used by Python and Java.
Implementation

      
 function timSort(arr, stats) {
  const n = arr.length;
  if (n < 2) return;
  const MIN_MERGE = 32;
  const MIN_GALLOP = 7;
  let minGallop = MIN_GALLOP;
  let tmp = new Array(n < 2 * MIN_MERGE ? n >>> 1 : 256);
  let tmpLen = tmp.length;
  const stackLen = n < 120 ? 5 : n < 1542 ? 10 : n < 119151 ? 24 : 49;
  const runBase = new Array(stackLen);
  const runLen = new Array(stackLen);
  let stackSize = 0;
  const metrics = stats.educational.metrics;
  const recordMetric = (name, delta = 1) => {
    metrics[name] = (metrics[name] || 0) + delta;
  };
  metrics.minMerge = MIN_MERGE;
  metrics.initialMinGallop = MIN_GALLOP;
  const compareValues = (left, right) => {
    if (left < right) return -1;
    if (left > right) return 1;
    return 0;
  };
  function writeValue(index, value) {
    arr[index] = value;
    recordMetric('writeOperations');
    write(index, value);
  }
  function swapValues(i, j) {
    const value = arr[i];
    arr[i] = arr[j];
    arr[j] = value;
    recordMetric('pairSwaps');
    swap(i, j);
  }
  function copyArray(src, srcPos, dest, destPos, length) {
    if (src === dest && srcPos < destPos && srcPos + length > destPos) {
      for (let i = length - 1; i >= 0; i--) {
        dest[destPos + i] = src[srcPos + i];
      }
      return;
    }
    for (let i = 0; i < length; i++) {
      dest[destPos + i] = src[srcPos + i];
    }
  }
  function copyTmpToArr(tmpPos, destPos, length) {
    for (let i = 0; i < length; i++) {
      writeValue(destPos + i, tmp[tmpPos + i]);
    }
  }
  function copyArrToArr(srcPos, destPos, length) {
    if (srcPos < destPos && srcPos + length > destPos) {
      for (let i = length - 1; i >= 0; i--) {
        writeValue(destPos + i, arr[srcPos + i]);
      }
      return;
    }
    for (let i = 0; i < length; i++) {
      writeValue(destPos + i, arr[srcPos + i]);
    }
  }
  function reverseRange(lo, hi) {
    hi--;
    while (lo < hi) {
      swapValues(lo, hi);
      lo++;
      hi--;
    }
    recordMetric('reversedRuns');
  }
  function binarySort(lo, hi, start) {
    if (start === lo) start++;
    for (; start < hi; start++) {
      const pivot = arr[start];
      let left = lo;
      let right = start;
      while (left < right) {
        const mid = left + right >>> 1;
        compare(start, mid);
        if (compareValues(pivot, arr[mid]) < 0) right = mid; else left = mid + 1;
      }
      for (let i = start; i > left; i--) {
        writeValue(i, arr[i - 1]);
      }
      writeValue(left, pivot);
      recordMetric('binaryInsertionPlacements');
    }
  }
  function countRunAndMakeAscending(lo, hi) {
    let runHi = lo + 1;
    if (runHi === hi) return 1;
    compare(runHi, lo);
    if (compareValues(arr[runHi], arr[lo]) < 0) {
      runHi++;
      while (runHi < hi) {
        compare(runHi, runHi - 1);
        if (!(compareValues(arr[runHi], arr[runHi - 1]) < 0)) break;
        runHi++;
      }
      reverseRange(lo, runHi);
    } else {
      runHi++;
      while (runHi < hi) {
        compare(runHi, runHi - 1);
        if (compareValues(arr[runHi], arr[runHi - 1]) < 0) break;
        runHi++;
      }
    }
    recordMetric('runsDetected');
    return runHi - lo;
  }
  function minRunLength(value) {
    let r = 0;
    while (value >= MIN_MERGE) {
      r |= value & 1;
      value >>= 1;
    }
    return value + r;
  }
  function pushRun(base, length) {
    runBase[stackSize] = base;
    runLen[stackSize] = length;
    stackSize++;
    recordMetric('stackPushes');
  }
  function gallopLeft(key, source, base, len, hint, keyIndex) {
    recordMetric('gallopLeftCalls');
    let lastOfs = 0;
    let ofs = 1;
    if (keyIndex >= 0 && source === arr) compare(keyIndex, base + hint);
    if (compareValues(key, source[base + hint]) > 0) {
      const maxOfs = len - hint;
      while (ofs < maxOfs) {
        if (keyIndex >= 0 && source === arr) compare(keyIndex, base + hint + ofs);
        if (!(compareValues(key, source[base + hint + ofs]) > 0)) break;
        lastOfs = ofs;
        ofs = (ofs << 1) + 1;
        if (ofs <= 0) ofs = maxOfs;
      }
      if (ofs > maxOfs) ofs = maxOfs;
      lastOfs += hint;
      ofs += hint;
    } else {
      const maxOfs = hint + 1;
      while (ofs < maxOfs) {
        if (keyIndex >= 0 && source === arr) compare(keyIndex, base + hint - ofs);
        if (!(compareValues(key, source[base + hint - ofs]) <= 0)) break;
        lastOfs = ofs;
        ofs = (ofs << 1) + 1;
        if (ofs <= 0) ofs = maxOfs;
      }
      if (ofs > maxOfs) ofs = maxOfs;
      const tmpOfs = lastOfs;
      lastOfs = hint - ofs;
      ofs = hint - tmpOfs;
    }
    lastOfs++;
    while (lastOfs < ofs) {
      const mid = lastOfs + (ofs - lastOfs >>> 1);
      if (keyIndex >= 0 && source === arr) compare(keyIndex, base + mid);
      if (compareValues(key, source[base + mid]) > 0) lastOfs = mid + 1; else ofs = mid;
    }
    return ofs;
  }
  function gallopRight(key, source, base, len, hint, keyIndex) {
    recordMetric('gallopRightCalls');
    let lastOfs = 0;
    let ofs = 1;
    if (keyIndex >= 0 && source === arr) compare(keyIndex, base + hint);
    if (compareValues(key, source[base + hint]) < 0) {
      const maxOfs = hint + 1;
      while (ofs < maxOfs) {
        if (keyIndex >= 0 && source === arr) compare(keyIndex, base + hint - ofs);
        if (!(compareValues(key, source[base + hint - ofs]) < 0)) break;
        lastOfs = ofs;
        ofs = (ofs << 1) + 1;
        if (ofs <= 0) ofs = maxOfs;
      }
      if (ofs > maxOfs) ofs = maxOfs;
      const tmpOfs = lastOfs;
      lastOfs = hint - ofs;
      ofs = hint - tmpOfs;
    } else {
      const maxOfs = len - hint;
      while (ofs < maxOfs) {
        if (keyIndex >= 0 && source === arr) compare(keyIndex, base + hint + ofs);
        if (!(compareValues(key, source[base + hint + ofs]) >= 0)) break;
        lastOfs = ofs;
        ofs = (ofs << 1) + 1;
        if (ofs <= 0) ofs = maxOfs;
      }
      if (ofs > maxOfs) ofs = maxOfs;
      lastOfs += hint;
      ofs += hint;
    }
    lastOfs++;
    while (lastOfs < ofs) {
      const mid = lastOfs + (ofs - lastOfs >>> 1);
      if (keyIndex >= 0 && source === arr) compare(keyIndex, base + mid);
      if (compareValues(key, source[base + mid]) < 0) ofs = mid; else lastOfs = mid + 1;
    }
    return ofs;
  }
  function ensureCapacity(minCapacity) {
    if (tmpLen >= minCapacity) return;
    let newSize = minCapacity;
    newSize |= newSize >> 1;
    newSize |= newSize >> 2;
    newSize |= newSize >> 4;
    newSize |= newSize >> 8;
    newSize |= newSize >> 16;
    newSize++;
    if (newSize < 0) newSize = minCapacity; else newSize = Math.max(minCapacity, Math.min(newSize, n >>> 1));
    tmp = new Array(newSize);
    tmpLen = newSize;
    recordMetric('tmpResizes');
  }
  function mergeLo(base1, len1, base2, len2) {
    recordMetric('mergeLoCalls');
    ensureCapacity(len1);
    copyArray(arr, base1, tmp, 0, len1);
    let cursor1 = 0;
    let cursor2 = base2;
    let dest = base1;
    writeValue(dest++, arr[cursor2++]);
    len2--;
    if (len2 === 0) {
      copyTmpToArr(cursor1, dest, len1);
      return;
    }
    if (len1 === 1) {
      copyArrToArr(cursor2, dest, len2);
      writeValue(dest + len2, tmp[cursor1]);
      return;
    }
    let localMinGallop = minGallop;
    while (true) {
      let count1 = 0;
      let count2 = 0;
      let exitOuter = false;
      do {
        if (compareValues(arr[cursor2], tmp[cursor1]) < 0) {
          writeValue(dest++, arr[cursor2++]);
          count2++;
          count1 = 0;
          len2--;
          if (len2 === 0) {
            exitOuter = true;
            break;
          }
        } else {
          writeValue(dest++, tmp[cursor1++]);
          count1++;
          count2 = 0;
          len1--;
          if (len1 === 1) {
            exitOuter = true;
            break;
          }
        }
      } while ((count1 | count2) < localMinGallop);
      if (exitOuter) break;
      do {
        count1 = gallopRight(arr[cursor2], tmp, cursor1, len1, 0, cursor2);
        if (count1 !== 0) {
          copyTmpToArr(cursor1, dest, count1);
          dest += count1;
          cursor1 += count1;
          len1 -= count1;
          if (len1 <= 1) {
            exitOuter = true;
            break;
          }
        }
        writeValue(dest++, arr[cursor2++]);
        len2--;
        if (len2 === 0) {
          exitOuter = true;
          break;
        }
        count2 = gallopLeft(tmp[cursor1], arr, cursor2, len2, 0, -1);
        if (count2 !== 0) {
          copyArrToArr(cursor2, dest, count2);
          dest += count2;
          cursor2 += count2;
          len2 -= count2;
          if (len2 === 0) {
            exitOuter = true;
            break;
          }
        }
        writeValue(dest++, tmp[cursor1++]);
        len1--;
        if (len1 === 1) {
          exitOuter = true;
          break;
        }
        localMinGallop--;
      } while (count1 >= MIN_GALLOP || count2 >= MIN_GALLOP);
      if (exitOuter) break;
      if (localMinGallop < 0) localMinGallop = 0;
      localMinGallop += 2;
    }
    minGallop = localMinGallop < 1 ? 1 : localMinGallop;
    metrics.finalMinGallop = minGallop;
    if (len1 === 1) {
      copyArrToArr(cursor2, dest, len2);
      writeValue(dest + len2, tmp[cursor1]);
    } else {
      copyTmpToArr(cursor1, dest, len1);
    }
  }
  function mergeHi(base1, len1, base2, len2) {
    recordMetric('mergeHiCalls');
    ensureCapacity(len2);
    copyArray(arr, base2, tmp, 0, len2);
    let cursor1 = base1 + len1 - 1;
    let cursor2 = len2 - 1;
    let dest = base2 + len2 - 1;
    writeValue(dest--, arr[cursor1--]);
    len1--;
    if (len1 === 0) {
      copyTmpToArr(0, dest - (len2 - 1), len2);
      return;
    }
    if (len2 === 1) {
      dest -= len1;
      cursor1 -= len1;
      copyArrToArr(cursor1 + 1, dest + 1, len1);
      writeValue(dest, tmp[cursor2]);
      return;
    }
    let localMinGallop = minGallop;
    while (true) {
      let count1 = 0;
      let count2 = 0;
      let exitOuter = false;
      do {
        if (compareValues(tmp[cursor2], arr[cursor1]) < 0) {
          writeValue(dest--, arr[cursor1--]);
          count1++;
          count2 = 0;
          len1--;
          if (len1 === 0) {
            exitOuter = true;
            break;
          }
        } else {
          writeValue(dest--, tmp[cursor2--]);
          count2++;
          count1 = 0;
          len2--;
          if (len2 === 1) {
            exitOuter = true;
            break;
          }
        }
      } while ((count1 | count2) < localMinGallop);
      if (exitOuter) break;
      do {
        const gallopRightOffset = gallopRight(tmp[cursor2], arr, base1, len1, len1 - 1, -1);
        count1 = len1 - gallopRightOffset;
        if (count1 !== 0) {
          dest -= count1;
          cursor1 -= count1;
          len1 -= count1;
          copyArrToArr(cursor1 + 1, dest + 1, count1);
          if (len1 === 0) {
            exitOuter = true;
            break;
          }
        }
        writeValue(dest--, tmp[cursor2--]);
        len2--;
        if (len2 === 1) {
          exitOuter = true;
          break;
        }
        const gallopLeftOffset = gallopLeft(arr[cursor1], tmp, 0, len2, len2 - 1, cursor1);
        count2 = len2 - gallopLeftOffset;
        if (count2 !== 0) {
          dest -= count2;
          cursor2 -= count2;
          len2 -= count2;
          copyTmpToArr(cursor2 + 1, dest + 1, count2);
          if (len2 <= 1) {
            exitOuter = true;
            break;
          }
        }
        writeValue(dest--, arr[cursor1--]);
        len1--;
        if (len1 === 0) {
          exitOuter = true;
          break;
        }
        localMinGallop--;
      } while (count1 >= MIN_GALLOP || count2 >= MIN_GALLOP);
      if (exitOuter) break;
      if (localMinGallop < 0) localMinGallop = 0;
      localMinGallop += 2;
    }
    minGallop = localMinGallop < 1 ? 1 : localMinGallop;
    metrics.finalMinGallop = minGallop;
    if (len2 === 1) {
      dest -= len1;
      cursor1 -= len1;
      copyArrToArr(cursor1 + 1, dest + 1, len1);
      writeValue(dest, tmp[cursor2]);
    } else {
      copyTmpToArr(0, dest - (len2 - 1), len2);
    }
  }
  function mergeAt(index) {
    recordMetric('mergeAtCalls');
    let base1 = runBase[index];
    let len1 = runLen[index];
    const base2 = runBase[index + 1];
    let len2 = runLen[index + 1];
    runLen[index] = len1 + len2;
    if (index === stackSize - 3) {
      runBase[index + 1] = runBase[index + 2];
      runLen[index + 1] = runLen[index + 2];
    }
    stackSize--;
    const k = gallopRight(arr[base2], arr, base1, len1, 0, base2);
    base1 += k;
    len1 -= k;
    if (len1 === 0) return;
    len2 = gallopLeft(arr[base1 + len1 - 1], arr, base2, len2, len2 - 1, base1 + len1 - 1);
    if (len2 === 0) return;
    if (len1 <= len2) mergeLo(base1, len1, base2, len2); else mergeHi(base1, len1, base2, len2);
  }
  function mergeCollapse() {
    while (stackSize > 1) {
      let index = stackSize - 2;
      if (index > 0 && runLen[index - 1] <= runLen[index] + runLen[index + 1] || index - 1 > 0 && runLen[index - 2] <= runLen[index - 1] + runLen[index]) {
        if (runLen[index - 1] < runLen[index + 1]) index--;
        mergeAt(index);
      } else if (runLen[index] <= runLen[index + 1]) {
        mergeAt(index);
      } else {
        break;
      }
    }
  }
  function mergeForceCollapse() {
    while (stackSize > 1) {
      let index = stackSize - 2;
      if (index > 0 && runLen[index - 1] < runLen[index + 1]) index--;
      mergeAt(index);
    }
  }
  let lo = 0;
  let remaining = n;
  if (remaining < MIN_MERGE) {
    const initRunLen = countRunAndMakeAscending(lo, n);
    binarySort(lo, n, lo + initRunLen);
    checkpoint(n, n);
    for (let i = 0; i < n; i++) markSorted(i);
    return;
  }
  const minRun = minRunLength(remaining);
  metrics.minRun = minRun;
  do {
    let currentRunLen = countRunAndMakeAscending(lo, n);
    if (currentRunLen < minRun) {
      const forcedRunLen = remaining <= minRun ? remaining : minRun;
      binarySort(lo, lo + forcedRunLen, lo + currentRunLen);
      currentRunLen = forcedRunLen;
      recordMetric('forcedRuns');
    }
    pushRun(lo, currentRunLen);
    mergeCollapse();
    lo += currentRunLen;
    remaining -= currentRunLen;
    checkpoint(lo, n);
  } while (remaining !== 0);
  mergeForceCollapse();
  checkpoint(n, n);
  for (let i = 0; i < n; i++) markSorted(i);
}
 def timSort(arr, stats):
    def recordMetric(name, ):
        metrics[name] = ((metrics[name] or 0) + delta)

    def compareValues(left, right):
        if (left < right):
            return -1
        if (left > right):
            return 1
        return 0

    def writeValue(index, value):
        arr[index] = value
        recordMetric("writeOperations")
        write(index, value)

    def swapValues(i, j):
        value = arr[i]
        arr[i] = arr[j]
        arr[j] = value
        recordMetric("pairSwaps")
        swap(i, j)

    def copyArray(src, srcPos, dest, destPos, length):
        if (((src == dest) and (srcPos < destPos)) and ((srcPos + length) > destPos)):
            for i in range((length - 1), (0 - 1), -1):
                dest[(destPos + i)] = src[(srcPos + i)]
            return
        for i in range(length):
            dest[(destPos + i)] = src[(srcPos + i)]

    def copyTmpToArr(tmpPos, destPos, length):
        for i in range(length):
            writeValue((destPos + i), tmp[(tmpPos + i)])

    def copyArrToArr(srcPos, destPos, length):
        if ((srcPos < destPos) and ((srcPos + length) > destPos)):
            for i in range((length - 1), (0 - 1), -1):
                writeValue((destPos + i), arr[(srcPos + i)])
            return
        for i in range(length):
            writeValue((destPos + i), arr[(srcPos + i)])

    def reverseRange(lo, hi):
        hi -= 1
        while (lo < hi):
            swapValues(lo, hi)
            lo += 1
            hi -= 1
        recordMetric("reversedRuns")

    def binarySort(lo, hi, start):
        if (start == lo):
            start += 1
        while (start < hi):
            pivot = arr[start]
            left = lo
            right = start
            while (left < right):
                mid = ((left + right) >> 1)
                compare(start, mid)
                if (compareValues(pivot, arr[mid]) < 0):
                    right = mid
                else:
                    left = (mid + 1)
            for i in range(start, left, -1):
                writeValue(i, arr[(i - 1)])
            writeValue(left, pivot)
            recordMetric("binaryInsertionPlacements")
            start += 1

    def countRunAndMakeAscending(lo, hi):
        runHi = (lo + 1)
        if (runHi == hi):
            return 1
        compare(runHi, lo)
        if (compareValues(arr[runHi], arr[lo]) < 0):
            runHi += 1
            while (runHi < hi):
                compare(runHi, (runHi - 1))
                if not (compareValues(arr[runHi], arr[(runHi - 1)]) < 0):
                    break
                runHi += 1
            reverseRange(lo, runHi)
        else:
            runHi += 1
            while (runHi < hi):
                compare(runHi, (runHi - 1))
                if (compareValues(arr[runHi], arr[(runHi - 1)]) < 0):
                    break
                runHi += 1
        recordMetric("runsDetected")
        return (runHi - lo)

    def minRunLength(value):
        r = 0
        while (value >= MIN_MERGE):
            r |= (value & 1)
            value >>= 1
        return (value + r)

    def pushRun(base, length):
        nonlocal stackSize
        runBase[stackSize] = base
        runLen[stackSize] = length
        stackSize += 1
        recordMetric("stackPushes")

    def gallopLeft(key, source, base, len, hint, keyIndex):
        recordMetric("gallopLeftCalls")
        lastOfs = 0
        ofs = 1
        if ((keyIndex >= 0) and (source == arr)):
            compare(keyIndex, (base + hint))
        if (compareValues(key, source[(base + hint)]) > 0):
            maxOfs = (len - hint)
            while (ofs < maxOfs):
                if ((keyIndex >= 0) and (source == arr)):
                    compare(keyIndex, ((base + hint) + ofs))
                if not (compareValues(key, source[((base + hint) + ofs)]) > 0):
                    break
                lastOfs = ofs
                ofs = ((ofs << 1) + 1)
                if (ofs <= 0):
                    ofs = maxOfs
            if (ofs > maxOfs):
                ofs = maxOfs
            lastOfs += hint
            ofs += hint
        else:
            maxOfs = (hint + 1)
            while (ofs < maxOfs):
                if ((keyIndex >= 0) and (source == arr)):
                    compare(keyIndex, ((base + hint) - ofs))
                if not (compareValues(key, source[((base + hint) - ofs)]) <= 0):
                    break
                lastOfs = ofs
                ofs = ((ofs << 1) + 1)
                if (ofs <= 0):
                    ofs = maxOfs
            if (ofs > maxOfs):
                ofs = maxOfs
            tmpOfs = lastOfs
            lastOfs = (hint - ofs)
            ofs = (hint - tmpOfs)
        lastOfs += 1
        while (lastOfs < ofs):
            mid = (lastOfs + ((ofs - lastOfs) >> 1))
            if ((keyIndex >= 0) and (source == arr)):
                compare(keyIndex, (base + mid))
            if (compareValues(key, source[(base + mid)]) > 0):
                lastOfs = (mid + 1)
            else:
                ofs = mid
        return ofs

    def gallopRight(key, source, base, len, hint, keyIndex):
        recordMetric("gallopRightCalls")
        lastOfs = 0
        ofs = 1
        if ((keyIndex >= 0) and (source == arr)):
            compare(keyIndex, (base + hint))
        if (compareValues(key, source[(base + hint)]) < 0):
            maxOfs = (hint + 1)
            while (ofs < maxOfs):
                if ((keyIndex >= 0) and (source == arr)):
                    compare(keyIndex, ((base + hint) - ofs))
                if not (compareValues(key, source[((base + hint) - ofs)]) < 0):
                    break
                lastOfs = ofs
                ofs = ((ofs << 1) + 1)
                if (ofs <= 0):
                    ofs = maxOfs
            if (ofs > maxOfs):
                ofs = maxOfs
            tmpOfs = lastOfs
            lastOfs = (hint - ofs)
            ofs = (hint - tmpOfs)
        else:
            maxOfs = (len - hint)
            while (ofs < maxOfs):
                if ((keyIndex >= 0) and (source == arr)):
                    compare(keyIndex, ((base + hint) + ofs))
                if not (compareValues(key, source[((base + hint) + ofs)]) >= 0):
                    break
                lastOfs = ofs
                ofs = ((ofs << 1) + 1)
                if (ofs <= 0):
                    ofs = maxOfs
            if (ofs > maxOfs):
                ofs = maxOfs
            lastOfs += hint
            ofs += hint
        lastOfs += 1
        while (lastOfs < ofs):
            mid = (lastOfs + ((ofs - lastOfs) >> 1))
            if ((keyIndex >= 0) and (source == arr)):
                compare(keyIndex, (base + mid))
            if (compareValues(key, source[(base + mid)]) < 0):
                ofs = mid
            else:
                lastOfs = (mid + 1)
        return ofs

    def ensureCapacity(minCapacity):
        nonlocal tmp, tmpLen
        if (tmpLen >= minCapacity):
            return
        newSize = minCapacity
        newSize |= (newSize >> 1)
        newSize |= (newSize >> 2)
        newSize |= (newSize >> 4)
        newSize |= (newSize >> 8)
        newSize |= (newSize >> 16)
        newSize += 1
        if (newSize < 0):
            newSize = minCapacity
        else:
            newSize = (minCapacity if minCapacity >= (newSize if newSize <= (n >> 1) else (n >> 1)) else (newSize if newSize <= (n >> 1) else (n >> 1)))
        tmp = [0] * newSize
        tmpLen = newSize
        recordMetric("tmpResizes")

    def mergeLo(base1, len1, base2, len2):
        nonlocal minGallop
        recordMetric("mergeLoCalls")
        ensureCapacity(len1)
        copyArray(arr, base1, tmp, 0, len1)
        cursor1 = 0
        cursor2 = base2
        dest = base1
        writeValue(((dest := dest + 1) - 1), arr[((cursor2 := cursor2 + 1) - 1)])
        len2 -= 1
        if (len2 == 0):
            copyTmpToArr(cursor1, dest, len1)
            return
        if (len1 == 1):
            copyArrToArr(cursor2, dest, len2)
            writeValue((dest + len2), tmp[cursor1])
            return
        localMinGallop = minGallop
        while True:
            count1 = 0
            count2 = 0
            exitOuter = False
            while True:
                if (compareValues(arr[cursor2], tmp[cursor1]) < 0):
                    writeValue(((dest := dest + 1) - 1), arr[((cursor2 := cursor2 + 1) - 1)])
                    count2 += 1
                    count1 = 0
                    len2 -= 1
                    if (len2 == 0):
                        exitOuter = True
                        break
                else:
                    writeValue(((dest := dest + 1) - 1), tmp[((cursor1 := cursor1 + 1) - 1)])
                    count1 += 1
                    count2 = 0
                    len1 -= 1
                    if (len1 == 1):
                        exitOuter = True
                        break
                if not (((count1 | count2) < localMinGallop)):
                    break
            if exitOuter:
                break
            while True:
                count1 = gallopRight(arr[cursor2], tmp, cursor1, len1, 0, cursor2)
                if (count1 != 0):
                    copyTmpToArr(cursor1, dest, count1)
                    dest += count1
                    cursor1 += count1
                    len1 -= count1
                    if (len1 <= 1):
                        exitOuter = True
                        break
                writeValue(((dest := dest + 1) - 1), arr[((cursor2 := cursor2 + 1) - 1)])
                len2 -= 1
                if (len2 == 0):
                    exitOuter = True
                    break
                count2 = gallopLeft(tmp[cursor1], arr, cursor2, len2, 0, -1)
                if (count2 != 0):
                    copyArrToArr(cursor2, dest, count2)
                    dest += count2
                    cursor2 += count2
                    len2 -= count2
                    if (len2 == 0):
                        exitOuter = True
                        break
                writeValue(((dest := dest + 1) - 1), tmp[((cursor1 := cursor1 + 1) - 1)])
                len1 -= 1
                if (len1 == 1):
                    exitOuter = True
                    break
                localMinGallop -= 1
                if not (((count1 >= MIN_GALLOP) or (count2 >= MIN_GALLOP))):
                    break
            if exitOuter:
                break
            if (localMinGallop < 0):
                localMinGallop = 0
            localMinGallop += 2
        minGallop = (1 if (localMinGallop < 1) else localMinGallop)
        metrics.finalMinGallop = minGallop
        if (len1 == 1):
            copyArrToArr(cursor2, dest, len2)
            writeValue((dest + len2), tmp[cursor1])
        else:
            copyTmpToArr(cursor1, dest, len1)

    def mergeHi(base1, len1, base2, len2):
        nonlocal minGallop
        recordMetric("mergeHiCalls")
        ensureCapacity(len2)
        copyArray(arr, base2, tmp, 0, len2)
        cursor1 = ((base1 + len1) - 1)
        cursor2 = (len2 - 1)
        dest = ((base2 + len2) - 1)
        writeValue(((dest := dest - 1) + 1), arr[((cursor1 := cursor1 - 1) + 1)])
        len1 -= 1
        if (len1 == 0):
            copyTmpToArr(0, (dest - (len2 - 1)), len2)
            return
        if (len2 == 1):
            dest -= len1
            cursor1 -= len1
            copyArrToArr((cursor1 + 1), (dest + 1), len1)
            writeValue(dest, tmp[cursor2])
            return
        localMinGallop = minGallop
        while True:
            count1 = 0
            count2 = 0
            exitOuter = False
            while True:
                if (compareValues(tmp[cursor2], arr[cursor1]) < 0):
                    writeValue(((dest := dest - 1) + 1), arr[((cursor1 := cursor1 - 1) + 1)])
                    count1 += 1
                    count2 = 0
                    len1 -= 1
                    if (len1 == 0):
                        exitOuter = True
                        break
                else:
                    writeValue(((dest := dest - 1) + 1), tmp[((cursor2 := cursor2 - 1) + 1)])
                    count2 += 1
                    count1 = 0
                    len2 -= 1
                    if (len2 == 1):
                        exitOuter = True
                        break
                if not (((count1 | count2) < localMinGallop)):
                    break
            if exitOuter:
                break
            while True:
                gallopRightOffset = gallopRight(tmp[cursor2], arr, base1, len1, (len1 - 1), -1)
                count1 = (len1 - gallopRightOffset)
                if (count1 != 0):
                    dest -= count1
                    cursor1 -= count1
                    len1 -= count1
                    copyArrToArr((cursor1 + 1), (dest + 1), count1)
                    if (len1 == 0):
                        exitOuter = True
                        break
                writeValue(((dest := dest - 1) + 1), tmp[((cursor2 := cursor2 - 1) + 1)])
                len2 -= 1
                if (len2 == 1):
                    exitOuter = True
                    break
                gallopLeftOffset = gallopLeft(arr[cursor1], tmp, 0, len2, (len2 - 1), cursor1)
                count2 = (len2 - gallopLeftOffset)
                if (count2 != 0):
                    dest -= count2
                    cursor2 -= count2
                    len2 -= count2
                    copyTmpToArr((cursor2 + 1), (dest + 1), count2)
                    if (len2 <= 1):
                        exitOuter = True
                        break
                writeValue(((dest := dest - 1) + 1), arr[((cursor1 := cursor1 - 1) + 1)])
                len1 -= 1
                if (len1 == 0):
                    exitOuter = True
                    break
                localMinGallop -= 1
                if not (((count1 >= MIN_GALLOP) or (count2 >= MIN_GALLOP))):
                    break
            if exitOuter:
                break
            if (localMinGallop < 0):
                localMinGallop = 0
            localMinGallop += 2
        minGallop = (1 if (localMinGallop < 1) else localMinGallop)
        metrics.finalMinGallop = minGallop
        if (len2 == 1):
            dest -= len1
            cursor1 -= len1
            copyArrToArr((cursor1 + 1), (dest + 1), len1)
            writeValue(dest, tmp[cursor2])
        else:
            copyTmpToArr(0, (dest - (len2 - 1)), len2)

    def mergeAt(index):
        nonlocal stackSize
        recordMetric("mergeAtCalls")
        base1 = runBase[index]
        len1 = runLen[index]
        base2 = runBase[(index + 1)]
        len2 = runLen[(index + 1)]
        runLen[index] = (len1 + len2)
        if (index == (stackSize - 3)):
            runBase[(index + 1)] = runBase[(index + 2)]
            runLen[(index + 1)] = runLen[(index + 2)]
        stackSize -= 1
        k = gallopRight(arr[base2], arr, base1, len1, 0, base2)
        base1 += k
        len1 -= k
        if (len1 == 0):
            return
        len2 = gallopLeft(arr[((base1 + len1) - 1)], arr, base2, len2, (len2 - 1), ((base1 + len1) - 1))
        if (len2 == 0):
            return
        if (len1 <= len2):
            mergeLo(base1, len1, base2, len2)
        else:
            mergeHi(base1, len1, base2, len2)

    def mergeCollapse():
        while (stackSize > 1):
            index = (stackSize - 2)
            if (((index > 0) and (runLen[(index - 1)] <= (runLen[index] + runLen[(index + 1)]))) or (((index - 1) > 0) and (runLen[(index - 2)] <= (runLen[(index - 1)] + runLen[index])))):
                if (runLen[(index - 1)] < runLen[(index + 1)]):
                    index -= 1
                mergeAt(index)
            elif (runLen[index] <= runLen[(index + 1)]):
                mergeAt(index)
            else:
                break

    def mergeForceCollapse():
        while (stackSize > 1):
            index = (stackSize - 2)
            if ((index > 0) and (runLen[(index - 1)] < runLen[(index + 1)])):
                index -= 1
            mergeAt(index)

    if (n < 2):
        return
    MIN_MERGE = 32
    MIN_GALLOP = 7
    minGallop = MIN_GALLOP
    tmp = [0] * ((n >> 1) if (n < (2 * MIN_MERGE)) else 256)
    tmpLen = len(tmp)
    stackLen = (5 if (n < 120) else (10 if (n < 1542) else (24 if (n < 119151) else 49)))
    runBase = [0] * stackLen
    runLen = [0] * stackLen
    stackSize = 0
    metrics.minMerge = MIN_MERGE
    metrics.initialMinGallop = MIN_GALLOP
    lo = 0
    remaining = n
    if (remaining < MIN_MERGE):
        initRunLen = countRunAndMakeAscending(lo, n)
        binarySort(lo, n, (lo + initRunLen))
        checkpoint(n, n)
        for i in range(n):
            markSorted(i)
        return
    minRun = minRunLength(remaining)
    metrics.minRun = minRun
    while True:
        currentRunLen = countRunAndMakeAscending(lo, n)
        if (currentRunLen < minRun):
            forcedRunLen = (remaining if (remaining <= minRun) else minRun)
            binarySort(lo, (lo + forcedRunLen), (lo + currentRunLen))
            currentRunLen = forcedRunLen
            recordMetric("forcedRuns")
        pushRun(lo, currentRunLen)
        mergeCollapse()
        lo += currentRunLen
        remaining -= currentRunLen
        checkpoint(lo, n)
        if not ((remaining != 0)):
            break
    mergeForceCollapse()
    checkpoint(n, n)
    for i in range(n):
        markSorted(i)
 #include <vector>
#include <algorithm>
void recordMetric(int name, int );
int compareValues(int left, int right);
void writeValue(int index, int value);
void swapValues(int i, int j);
void copyArray(int src, int srcPos, int dest, int destPos, int length);
void copyTmpToArr(int tmpPos, int destPos, int length);
void copyArrToArr(int srcPos, int destPos, int length);
void reverseRange(int lo, int hi);
void binarySort(int lo, int hi, int start);
int countRunAndMakeAscending(int lo, int hi);
int minRunLength(int value);
void pushRun(int base, int length);
int gallopLeft(int key, int source, int base, int len, int hint, int keyIndex);
int gallopRight(int key, int source, int base, int len, int hint, int keyIndex);
void ensureCapacity(int minCapacity);
void mergeLo(int base1, int len1, int base2, int len2);
void mergeHi(int base1, int len1, int base2, int len2);
void mergeAt(int index);
void mergeCollapse();
void mergeForceCollapse();

void recordMetric(int name, int ) {
    metrics[name] = (((metrics[name]) != 0 ? (metrics[name]) : (0)) + delta);
}

int compareValues(int left, int right) {
    if((left < right)) {
        return -1;
    }
    if((left > right)) {
        return 1;
    }
    return 0;
}

void writeValue(int index, int value) {
    arr[index] = value;
    recordMetric("writeOperations");
    write(index, value);
}

void swapValues(int i, int j) {
    int value = arr[i];
    arr[i] = arr[j];
    arr[j] = value;
    recordMetric("pairSwaps");
    swap(i, j);
}

void copyArray(int src, int srcPos, int dest, int destPos, int length) {
    if((((src == dest) && (srcPos < destPos)) && ((srcPos + length) > destPos))) {
        for(int i=(length - 1); i>(0 - 1); i--) {
            dest[(destPos + i)] = src[(srcPos + i)];
        }
        return;
    }
    for(int i=0; i<length; i++) {
        dest[(destPos + i)] = src[(srcPos + i)];
    }
}

void copyTmpToArr(int tmpPos, int destPos, int length) {
    for(int i=0; i<length; i++) {
        writeValue((destPos + i), tmp[(tmpPos + i)]);
    }
}

void copyArrToArr(int srcPos, int destPos, int length) {
    if(((srcPos < destPos) && ((srcPos + length) > destPos))) {
        for(int i=(length - 1); i>(0 - 1); i--) {
            writeValue((destPos + i), arr[(srcPos + i)]);
        }
        return;
    }
    for(int i=0; i<length; i++) {
        writeValue((destPos + i), arr[(srcPos + i)]);
    }
}

void reverseRange(int lo, int hi) {
    hi--;
    while((lo < hi)) {
        swapValues(lo, hi);
        lo++;
        hi--;
    }
    recordMetric("reversedRuns");
}

void binarySort(int lo, int hi, int start) {
    if((start == lo)) {
        start++;
    }
    for(; (start < hi); start++) {
        int pivot = arr[start];
        int left = lo;
        int right = start;
        while((left < right)) {
            int mid = ((left + right) >>> 1);
            compare(start, mid);
            if((compareValues(pivot, arr[mid]) < 0)) {
                right = mid;
            } else {
                left = (mid + 1);
            }
        }
        for(int i=start; i>left; i--) {
            writeValue(i, arr[(i - 1)]);
        }
        writeValue(left, pivot);
        recordMetric("binaryInsertionPlacements");
    }
}

int countRunAndMakeAscending(int lo, int hi) {
    int runHi = (lo + 1);
    if((runHi == hi)) {
        return 1;
    }
    compare(runHi, lo);
    if((compareValues(arr[runHi], arr[lo]) < 0)) {
        runHi++;
        while((runHi < hi)) {
            compare(runHi, (runHi - 1));
            if(!(compareValues(arr[runHi], arr[(runHi - 1)]) < 0)) {
                break;
            }
            runHi++;
        }
        reverseRange(lo, runHi);
    } else {
        runHi++;
        while((runHi < hi)) {
            compare(runHi, (runHi - 1));
            if((compareValues(arr[runHi], arr[(runHi - 1)]) < 0)) {
                break;
            }
            runHi++;
        }
    }
    recordMetric("runsDetected");
    return (runHi - lo);
}

int minRunLength(int value) {
    int r = 0;
    while((value >= MIN_MERGE)) {
        r |= (value & 1);
        value >>= 1;
    }
    return (value + r);
}

void pushRun(int base, int length) {
    runBase[stackSize] = base;
    runLen[stackSize] = length;
    stackSize++;
    recordMetric("stackPushes");
}

int gallopLeft(int key, int source, int base, int len, int hint, int keyIndex) {
    recordMetric("gallopLeftCalls");
    int lastOfs = 0;
    int ofs = 1;
    if(((keyIndex >= 0) && (source == arr))) {
        compare(keyIndex, (base + hint));
    }
    if((compareValues(key, source[(base + hint)]) > 0)) {
        int maxOfs = (len - hint);
        while((ofs < maxOfs)) {
            if(((keyIndex >= 0) && (source == arr))) {
                compare(keyIndex, ((base + hint) + ofs));
            }
            if(!(compareValues(key, source[((base + hint) + ofs)]) > 0)) {
                break;
            }
            lastOfs = ofs;
            ofs = ((ofs << 1) + 1);
            if((ofs <= 0)) {
                ofs = maxOfs;
            }
        }
        if((ofs > maxOfs)) {
            ofs = maxOfs;
        }
        lastOfs += hint;
        ofs += hint;
    } else {
        int maxOfs = (hint + 1);
        while((ofs < maxOfs)) {
            if(((keyIndex >= 0) && (source == arr))) {
                compare(keyIndex, ((base + hint) - ofs));
            }
            if(!(compareValues(key, source[((base + hint) - ofs)]) <= 0)) {
                break;
            }
            lastOfs = ofs;
            ofs = ((ofs << 1) + 1);
            if((ofs <= 0)) {
                ofs = maxOfs;
            }
        }
        if((ofs > maxOfs)) {
            ofs = maxOfs;
        }
        int tmpOfs = lastOfs;
        lastOfs = (hint - ofs);
        ofs = (hint - tmpOfs);
    }
    lastOfs++;
    while((lastOfs < ofs)) {
        int mid = (lastOfs + ((ofs - lastOfs) >>> 1));
        if(((keyIndex >= 0) && (source == arr))) {
            compare(keyIndex, (base + mid));
        }
        if((compareValues(key, source[(base + mid)]) > 0)) {
            lastOfs = (mid + 1);
        } else {
            ofs = mid;
        }
    }
    return ofs;
}

int gallopRight(int key, int source, int base, int len, int hint, int keyIndex) {
    recordMetric("gallopRightCalls");
    int lastOfs = 0;
    int ofs = 1;
    if(((keyIndex >= 0) && (source == arr))) {
        compare(keyIndex, (base + hint));
    }
    if((compareValues(key, source[(base + hint)]) < 0)) {
        int maxOfs = (hint + 1);
        while((ofs < maxOfs)) {
            if(((keyIndex >= 0) && (source == arr))) {
                compare(keyIndex, ((base + hint) - ofs));
            }
            if(!(compareValues(key, source[((base + hint) - ofs)]) < 0)) {
                break;
            }
            lastOfs = ofs;
            ofs = ((ofs << 1) + 1);
            if((ofs <= 0)) {
                ofs = maxOfs;
            }
        }
        if((ofs > maxOfs)) {
            ofs = maxOfs;
        }
        int tmpOfs = lastOfs;
        lastOfs = (hint - ofs);
        ofs = (hint - tmpOfs);
    } else {
        int maxOfs = (len - hint);
        while((ofs < maxOfs)) {
            if(((keyIndex >= 0) && (source == arr))) {
                compare(keyIndex, ((base + hint) + ofs));
            }
            if(!(compareValues(key, source[((base + hint) + ofs)]) >= 0)) {
                break;
            }
            lastOfs = ofs;
            ofs = ((ofs << 1) + 1);
            if((ofs <= 0)) {
                ofs = maxOfs;
            }
        }
        if((ofs > maxOfs)) {
            ofs = maxOfs;
        }
        lastOfs += hint;
        ofs += hint;
    }
    lastOfs++;
    while((lastOfs < ofs)) {
        int mid = (lastOfs + ((ofs - lastOfs) >>> 1));
        if(((keyIndex >= 0) && (source == arr))) {
            compare(keyIndex, (base + mid));
        }
        if((compareValues(key, source[(base + mid)]) < 0)) {
            ofs = mid;
        } else {
            lastOfs = (mid + 1);
        }
    }
    return ofs;
}

void ensureCapacity(int minCapacity) {
    if((tmpLen >= minCapacity)) {
        return;
    }
    int newSize = minCapacity;
    newSize |= (newSize >> 1);
    newSize |= (newSize >> 2);
    newSize |= (newSize >> 4);
    newSize |= (newSize >> 8);
    newSize |= (newSize >> 16);
    newSize++;
    if((newSize < 0)) {
        newSize = minCapacity;
    } else {
        newSize = ((minCapacity) > (((newSize) < ((n >>> 1)) ? (newSize) : ((n >>> 1)))) ? (minCapacity) : (((newSize) < ((n >>> 1)) ? (newSize) : ((n >>> 1)))));
    }
    tmp = std::vector<int>(newSize);
    tmpLen = newSize;
    recordMetric("tmpResizes");
}

void mergeLo(int base1, int len1, int base2, int len2) {
    recordMetric("mergeLoCalls");
    ensureCapacity(len1);
    copyArray(arr, base1, tmp, 0, len1);
    int cursor1 = 0;
    int cursor2 = base2;
    int dest = base1;
    writeValue(dest++, arr[cursor2++]);
    len2--;
    if((len2 == 0)) {
        copyTmpToArr(cursor1, dest, len1);
        return;
    }
    if((len1 == 1)) {
        copyArrToArr(cursor2, dest, len2);
        writeValue((dest + len2), tmp[cursor1]);
        return;
    }
    int localMinGallop = minGallop;
    while(1) {
        int count1 = 0;
        int count2 = 0;
        int exitOuter = 0;
        do {
            if((compareValues(arr[cursor2], tmp[cursor1]) < 0)) {
                writeValue(dest++, arr[cursor2++]);
                count2++;
                count1 = 0;
                len2--;
                if((len2 == 0)) {
                    exitOuter = 1;
                    break;
                }
            } else {
                writeValue(dest++, tmp[cursor1++]);
                count1++;
                count2 = 0;
                len1--;
                if((len1 == 1)) {
                    exitOuter = 1;
                    break;
                }
            }
        } while(((count1 | count2) < localMinGallop));
        if(exitOuter) {
            break;
        }
        do {
            count1 = gallopRight(arr[cursor2], tmp, cursor1, len1, 0, cursor2);
            if((count1 != 0)) {
                copyTmpToArr(cursor1, dest, count1);
                dest += count1;
                cursor1 += count1;
                len1 -= count1;
                if((len1 <= 1)) {
                    exitOuter = 1;
                    break;
                }
            }
            writeValue(dest++, arr[cursor2++]);
            len2--;
            if((len2 == 0)) {
                exitOuter = 1;
                break;
            }
            count2 = gallopLeft(tmp[cursor1], arr, cursor2, len2, 0, -1);
            if((count2 != 0)) {
                copyArrToArr(cursor2, dest, count2);
                dest += count2;
                cursor2 += count2;
                len2 -= count2;
                if((len2 == 0)) {
                    exitOuter = 1;
                    break;
                }
            }
            writeValue(dest++, tmp[cursor1++]);
            len1--;
            if((len1 == 1)) {
                exitOuter = 1;
                break;
            }
            localMinGallop--;
        } while(((count1 >= MIN_GALLOP) || (count2 >= MIN_GALLOP)));
        if(exitOuter) {
            break;
        }
        if((localMinGallop < 0)) {
            localMinGallop = 0;
        }
        localMinGallop += 2;
    }
    minGallop = (((localMinGallop < 1)) ? (1) : (localMinGallop));
    metrics.finalMinGallop = minGallop;
    if((len1 == 1)) {
        copyArrToArr(cursor2, dest, len2);
        writeValue((dest + len2), tmp[cursor1]);
    } else {
        copyTmpToArr(cursor1, dest, len1);
    }
}

void mergeHi(int base1, int len1, int base2, int len2) {
    recordMetric("mergeHiCalls");
    ensureCapacity(len2);
    copyArray(arr, base2, tmp, 0, len2);
    int cursor1 = ((base1 + len1) - 1);
    int cursor2 = (len2 - 1);
    int dest = ((base2 + len2) - 1);
    writeValue(dest--, arr[cursor1--]);
    len1--;
    if((len1 == 0)) {
        copyTmpToArr(0, (dest - (len2 - 1)), len2);
        return;
    }
    if((len2 == 1)) {
        dest -= len1;
        cursor1 -= len1;
        copyArrToArr((cursor1 + 1), (dest + 1), len1);
        writeValue(dest, tmp[cursor2]);
        return;
    }
    int localMinGallop = minGallop;
    while(1) {
        int count1 = 0;
        int count2 = 0;
        int exitOuter = 0;
        do {
            if((compareValues(tmp[cursor2], arr[cursor1]) < 0)) {
                writeValue(dest--, arr[cursor1--]);
                count1++;
                count2 = 0;
                len1--;
                if((len1 == 0)) {
                    exitOuter = 1;
                    break;
                }
            } else {
                writeValue(dest--, tmp[cursor2--]);
                count2++;
                count1 = 0;
                len2--;
                if((len2 == 1)) {
                    exitOuter = 1;
                    break;
                }
            }
        } while(((count1 | count2) < localMinGallop));
        if(exitOuter) {
            break;
        }
        do {
            int gallopRightOffset = gallopRight(tmp[cursor2], arr, base1, len1, (len1 - 1), -1);
            count1 = (len1 - gallopRightOffset);
            if((count1 != 0)) {
                dest -= count1;
                cursor1 -= count1;
                len1 -= count1;
                copyArrToArr((cursor1 + 1), (dest + 1), count1);
                if((len1 == 0)) {
                    exitOuter = 1;
                    break;
                }
            }
            writeValue(dest--, tmp[cursor2--]);
            len2--;
            if((len2 == 1)) {
                exitOuter = 1;
                break;
            }
            int gallopLeftOffset = gallopLeft(arr[cursor1], tmp, 0, len2, (len2 - 1), cursor1);
            count2 = (len2 - gallopLeftOffset);
            if((count2 != 0)) {
                dest -= count2;
                cursor2 -= count2;
                len2 -= count2;
                copyTmpToArr((cursor2 + 1), (dest + 1), count2);
                if((len2 <= 1)) {
                    exitOuter = 1;
                    break;
                }
            }
            writeValue(dest--, arr[cursor1--]);
            len1--;
            if((len1 == 0)) {
                exitOuter = 1;
                break;
            }
            localMinGallop--;
        } while(((count1 >= MIN_GALLOP) || (count2 >= MIN_GALLOP)));
        if(exitOuter) {
            break;
        }
        if((localMinGallop < 0)) {
            localMinGallop = 0;
        }
        localMinGallop += 2;
    }
    minGallop = (((localMinGallop < 1)) ? (1) : (localMinGallop));
    metrics.finalMinGallop = minGallop;
    if((len2 == 1)) {
        dest -= len1;
        cursor1 -= len1;
        copyArrToArr((cursor1 + 1), (dest + 1), len1);
        writeValue(dest, tmp[cursor2]);
    } else {
        copyTmpToArr(0, (dest - (len2 - 1)), len2);
    }
}

void mergeAt(int index) {
    recordMetric("mergeAtCalls");
    int base1 = runBase[index];
    int len1 = runLen[index];
    int base2 = runBase[(index + 1)];
    int len2 = runLen[(index + 1)];
    runLen[index] = (len1 + len2);
    if((index == (stackSize - 3))) {
        runBase[(index + 1)] = runBase[(index + 2)];
        runLen[(index + 1)] = runLen[(index + 2)];
    }
    stackSize--;
    int k = gallopRight(arr[base2], arr, base1, len1, 0, base2);
    base1 += k;
    len1 -= k;
    if((len1 == 0)) {
        return;
    }
    len2 = gallopLeft(arr[((base1 + len1) - 1)], arr, base2, len2, (len2 - 1), ((base1 + len1) - 1));
    if((len2 == 0)) {
        return;
    }
    if((len1 <= len2)) {
        mergeLo(base1, len1, base2, len2);
    } else {
        mergeHi(base1, len1, base2, len2);
    }
}

void mergeCollapse() {
    while((stackSize > 1)) {
        int index = (stackSize - 2);
        if((((index > 0) && (runLen[(index - 1)] <= (runLen[index] + runLen[(index + 1)]))) || (((index - 1) > 0) && (runLen[(index - 2)] <= (runLen[(index - 1)] + runLen[index]))))) {
            if((runLen[(index - 1)] < runLen[(index + 1)])) {
                index--;
            }
            mergeAt(index);
        } else if((runLen[index] <= runLen[(index + 1)])) {
            mergeAt(index);
        } else {
            break;
        }
    }
}

void mergeForceCollapse() {
    while((stackSize > 1)) {
        int index = (stackSize - 2);
        if(((index > 0) && (runLen[(index - 1)] < runLen[(index + 1)]))) {
            index--;
        }
        mergeAt(index);
    }
}

void sort(std::vector<int>& arr, int n, int& comparisons, int& swaps) {
    if((n < 2)) {
        return;
    }
    int MIN_MERGE = 32;
    int MIN_GALLOP = 7;
    int minGallop = MIN_GALLOP;
    std::vector<int> tmp((((n < (2 * MIN_MERGE))) ? ((n >>> 1)) : (256)), 0);
    int tmpLen = n;
    int stackLen = (((n < 120)) ? (5) : ((((n < 1542)) ? (10) : ((((n < 119151)) ? (24) : (49))))));
    std::vector<int> runBase(stackLen, 0);
    std::vector<int> runLen(stackLen, 0);
    int stackSize = 0;
    int metrics = educational.metrics;
    metrics.minMerge = MIN_MERGE;
    metrics.initialMinGallop = MIN_GALLOP;
    int lo = 0;
    int remaining = n;
    if((remaining < MIN_MERGE)) {
        int initRunLen = countRunAndMakeAscending(lo, n);
        binarySort(lo, n, (lo + initRunLen));
        checkpoint(n, n);
        for(int i=0; i<n; i++) {
            markSorted(i);
        }
        return;
    }
    int minRun = minRunLength(remaining);
    metrics.minRun = minRun;
    do {
        int currentRunLen = countRunAndMakeAscending(lo, n);
        if((currentRunLen < minRun)) {
            int forcedRunLen = (((remaining <= minRun)) ? (remaining) : (minRun));
            binarySort(lo, (lo + forcedRunLen), (lo + currentRunLen));
            currentRunLen = forcedRunLen;
            recordMetric("forcedRuns");
        }
        pushRun(lo, currentRunLen);
        mergeCollapse();
        lo += currentRunLen;
        remaining -= currentRunLen;
        checkpoint(lo, n);
    } while((remaining != 0));
    mergeForceCollapse();
    checkpoint(n, n);
    for(int i=0; i<n; i++) {
        markSorted(i);
    }
} void recordMetric(int name, int ) {
    metrics[name] = (((metrics[name]) != 0 ? (metrics[name]) : (0)) + delta);
}

int compareValues(int left, int right) {
    if((left < right)) {
        return -1;
    }
    if((left > right)) {
        return 1;
    }
    return 0;
}

void writeValue(int index, int value) {
    arr[index] = value;
    recordMetric("writeOperations");
    write(index, value);
}

void swapValues(int i, int j) {
    int value = arr[i];
    arr[i] = arr[j];
    arr[j] = value;
    recordMetric("pairSwaps");
    swap(i, j);
}

void copyArray(int src, int srcPos, int dest, int destPos, int length) {
    if((((src == dest) && (srcPos < destPos)) && ((srcPos + length) > destPos))) {
        for(int i=(length - 1); i>(0 - 1); i--) {
            dest[(destPos + i)] = src[(srcPos + i)];
        }
        return;
    }
    for(int i=0; i<length; i++) {
        dest[(destPos + i)] = src[(srcPos + i)];
    }
}

void copyTmpToArr(int tmpPos, int destPos, int length) {
    for(int i=0; i<length; i++) {
        writeValue((destPos + i), tmp[(tmpPos + i)]);
    }
}

void copyArrToArr(int srcPos, int destPos, int length) {
    if(((srcPos < destPos) && ((srcPos + length) > destPos))) {
        for(int i=(length - 1); i>(0 - 1); i--) {
            writeValue((destPos + i), arr[(srcPos + i)]);
        }
        return;
    }
    for(int i=0; i<length; i++) {
        writeValue((destPos + i), arr[(srcPos + i)]);
    }
}

void reverseRange(int lo, int hi) {
    hi--;
    while((lo < hi)) {
        swapValues(lo, hi);
        lo++;
        hi--;
    }
    recordMetric("reversedRuns");
}

void binarySort(int lo, int hi, int start) {
    if((start == lo)) {
        start++;
    }
    for(; (start < hi); start++) {
        int pivot = arr[start];
        int left = lo;
        int right = start;
        while((left < right)) {
            int mid = ((left + right) >>> 1);
            compare(start, mid);
            if((compareValues(pivot, arr[mid]) < 0)) {
                right = mid;
            } else {
                left = (mid + 1);
            }
        }
        for(int i=start; i>left; i--) {
            writeValue(i, arr[(i - 1)]);
        }
        writeValue(left, pivot);
        recordMetric("binaryInsertionPlacements");
    }
}

int countRunAndMakeAscending(int lo, int hi) {
    int runHi = (lo + 1);
    if((runHi == hi)) {
        return 1;
    }
    compare(runHi, lo);
    if((compareValues(arr[runHi], arr[lo]) < 0)) {
        runHi++;
        while((runHi < hi)) {
            compare(runHi, (runHi - 1));
            if(!(compareValues(arr[runHi], arr[(runHi - 1)]) < 0)) {
                break;
            }
            runHi++;
        }
        reverseRange(lo, runHi);
    } else {
        runHi++;
        while((runHi < hi)) {
            compare(runHi, (runHi - 1));
            if((compareValues(arr[runHi], arr[(runHi - 1)]) < 0)) {
                break;
            }
            runHi++;
        }
    }
    recordMetric("runsDetected");
    return (runHi - lo);
}

int minRunLength(int value) {
    int r = 0;
    while((value >= MIN_MERGE)) {
        r |= (value & 1);
        value >>= 1;
    }
    return (value + r);
}

void pushRun(int base, int length) {
    runBase[stackSize] = base;
    runLen[stackSize] = length;
    stackSize++;
    recordMetric("stackPushes");
}

int gallopLeft(int key, int source, int base, int len, int hint, int keyIndex) {
    recordMetric("gallopLeftCalls");
    int lastOfs = 0;
    int ofs = 1;
    if(((keyIndex >= 0) && (source == arr))) {
        compare(keyIndex, (base + hint));
    }
    if((compareValues(key, source[(base + hint)]) > 0)) {
        int maxOfs = (len - hint);
        while((ofs < maxOfs)) {
            if(((keyIndex >= 0) && (source == arr))) {
                compare(keyIndex, ((base + hint) + ofs));
            }
            if(!(compareValues(key, source[((base + hint) + ofs)]) > 0)) {
                break;
            }
            lastOfs = ofs;
            ofs = ((ofs << 1) + 1);
            if((ofs <= 0)) {
                ofs = maxOfs;
            }
        }
        if((ofs > maxOfs)) {
            ofs = maxOfs;
        }
        lastOfs += hint;
        ofs += hint;
    } else {
        int maxOfs = (hint + 1);
        while((ofs < maxOfs)) {
            if(((keyIndex >= 0) && (source == arr))) {
                compare(keyIndex, ((base + hint) - ofs));
            }
            if(!(compareValues(key, source[((base + hint) - ofs)]) <= 0)) {
                break;
            }
            lastOfs = ofs;
            ofs = ((ofs << 1) + 1);
            if((ofs <= 0)) {
                ofs = maxOfs;
            }
        }
        if((ofs > maxOfs)) {
            ofs = maxOfs;
        }
        int tmpOfs = lastOfs;
        lastOfs = (hint - ofs);
        ofs = (hint - tmpOfs);
    }
    lastOfs++;
    while((lastOfs < ofs)) {
        int mid = (lastOfs + ((ofs - lastOfs) >>> 1));
        if(((keyIndex >= 0) && (source == arr))) {
            compare(keyIndex, (base + mid));
        }
        if((compareValues(key, source[(base + mid)]) > 0)) {
            lastOfs = (mid + 1);
        } else {
            ofs = mid;
        }
    }
    return ofs;
}

int gallopRight(int key, int source, int base, int len, int hint, int keyIndex) {
    recordMetric("gallopRightCalls");
    int lastOfs = 0;
    int ofs = 1;
    if(((keyIndex >= 0) && (source == arr))) {
        compare(keyIndex, (base + hint));
    }
    if((compareValues(key, source[(base + hint)]) < 0)) {
        int maxOfs = (hint + 1);
        while((ofs < maxOfs)) {
            if(((keyIndex >= 0) && (source == arr))) {
                compare(keyIndex, ((base + hint) - ofs));
            }
            if(!(compareValues(key, source[((base + hint) - ofs)]) < 0)) {
                break;
            }
            lastOfs = ofs;
            ofs = ((ofs << 1) + 1);
            if((ofs <= 0)) {
                ofs = maxOfs;
            }
        }
        if((ofs > maxOfs)) {
            ofs = maxOfs;
        }
        int tmpOfs = lastOfs;
        lastOfs = (hint - ofs);
        ofs = (hint - tmpOfs);
    } else {
        int maxOfs = (len - hint);
        while((ofs < maxOfs)) {
            if(((keyIndex >= 0) && (source == arr))) {
                compare(keyIndex, ((base + hint) + ofs));
            }
            if(!(compareValues(key, source[((base + hint) + ofs)]) >= 0)) {
                break;
            }
            lastOfs = ofs;
            ofs = ((ofs << 1) + 1);
            if((ofs <= 0)) {
                ofs = maxOfs;
            }
        }
        if((ofs > maxOfs)) {
            ofs = maxOfs;
        }
        lastOfs += hint;
        ofs += hint;
    }
    lastOfs++;
    while((lastOfs < ofs)) {
        int mid = (lastOfs + ((ofs - lastOfs) >>> 1));
        if(((keyIndex >= 0) && (source == arr))) {
            compare(keyIndex, (base + mid));
        }
        if((compareValues(key, source[(base + mid)]) < 0)) {
            ofs = mid;
        } else {
            lastOfs = (mid + 1);
        }
    }
    return ofs;
}

void ensureCapacity(int minCapacity) {
    if((tmpLen >= minCapacity)) {
        return;
    }
    int newSize = minCapacity;
    newSize |= (newSize >> 1);
    newSize |= (newSize >> 2);
    newSize |= (newSize >> 4);
    newSize |= (newSize >> 8);
    newSize |= (newSize >> 16);
    newSize++;
    if((newSize < 0)) {
        newSize = minCapacity;
    } else {
        newSize = Math.Max(minCapacity, Math.Min(newSize, (n >>> 1)));
    }
    tmp = new int[newSize];
    tmpLen = newSize;
    recordMetric("tmpResizes");
}

void mergeLo(int base1, int len1, int base2, int len2) {
    recordMetric("mergeLoCalls");
    ensureCapacity(len1);
    copyArray(arr, base1, tmp, 0, len1);
    int cursor1 = 0;
    int cursor2 = base2;
    int dest = base1;
    writeValue(dest++, arr[cursor2++]);
    len2--;
    if((len2 == 0)) {
        copyTmpToArr(cursor1, dest, len1);
        return;
    }
    if((len1 == 1)) {
        copyArrToArr(cursor2, dest, len2);
        writeValue((dest + len2), tmp[cursor1]);
        return;
    }
    int localMinGallop = minGallop;
    while(true) {
        int count1 = 0;
        int count2 = 0;
        int exitOuter = false;
        do {
            if((compareValues(arr[cursor2], tmp[cursor1]) < 0)) {
                writeValue(dest++, arr[cursor2++]);
                count2++;
                count1 = 0;
                len2--;
                if((len2 == 0)) {
                    exitOuter = true;
                    break;
                }
            } else {
                writeValue(dest++, tmp[cursor1++]);
                count1++;
                count2 = 0;
                len1--;
                if((len1 == 1)) {
                    exitOuter = true;
                    break;
                }
            }
        } while(((count1 | count2) < localMinGallop));
        if(exitOuter) {
            break;
        }
        do {
            count1 = gallopRight(arr[cursor2], tmp, cursor1, len1, 0, cursor2);
            if((count1 != 0)) {
                copyTmpToArr(cursor1, dest, count1);
                dest += count1;
                cursor1 += count1;
                len1 -= count1;
                if((len1 <= 1)) {
                    exitOuter = true;
                    break;
                }
            }
            writeValue(dest++, arr[cursor2++]);
            len2--;
            if((len2 == 0)) {
                exitOuter = true;
                break;
            }
            count2 = gallopLeft(tmp[cursor1], arr, cursor2, len2, 0, -1);
            if((count2 != 0)) {
                copyArrToArr(cursor2, dest, count2);
                dest += count2;
                cursor2 += count2;
                len2 -= count2;
                if((len2 == 0)) {
                    exitOuter = true;
                    break;
                }
            }
            writeValue(dest++, tmp[cursor1++]);
            len1--;
            if((len1 == 1)) {
                exitOuter = true;
                break;
            }
            localMinGallop--;
        } while(((count1 >= MIN_GALLOP) || (count2 >= MIN_GALLOP)));
        if(exitOuter) {
            break;
        }
        if((localMinGallop < 0)) {
            localMinGallop = 0;
        }
        localMinGallop += 2;
    }
    minGallop = (((localMinGallop < 1)) ? (1) : (localMinGallop));
    metrics.finalMinGallop = minGallop;
    if((len1 == 1)) {
        copyArrToArr(cursor2, dest, len2);
        writeValue((dest + len2), tmp[cursor1]);
    } else {
        copyTmpToArr(cursor1, dest, len1);
    }
}

void mergeHi(int base1, int len1, int base2, int len2) {
    recordMetric("mergeHiCalls");
    ensureCapacity(len2);
    copyArray(arr, base2, tmp, 0, len2);
    int cursor1 = ((base1 + len1) - 1);
    int cursor2 = (len2 - 1);
    int dest = ((base2 + len2) - 1);
    writeValue(dest--, arr[cursor1--]);
    len1--;
    if((len1 == 0)) {
        copyTmpToArr(0, (dest - (len2 - 1)), len2);
        return;
    }
    if((len2 == 1)) {
        dest -= len1;
        cursor1 -= len1;
        copyArrToArr((cursor1 + 1), (dest + 1), len1);
        writeValue(dest, tmp[cursor2]);
        return;
    }
    int localMinGallop = minGallop;
    while(true) {
        int count1 = 0;
        int count2 = 0;
        int exitOuter = false;
        do {
            if((compareValues(tmp[cursor2], arr[cursor1]) < 0)) {
                writeValue(dest--, arr[cursor1--]);
                count1++;
                count2 = 0;
                len1--;
                if((len1 == 0)) {
                    exitOuter = true;
                    break;
                }
            } else {
                writeValue(dest--, tmp[cursor2--]);
                count2++;
                count1 = 0;
                len2--;
                if((len2 == 1)) {
                    exitOuter = true;
                    break;
                }
            }
        } while(((count1 | count2) < localMinGallop));
        if(exitOuter) {
            break;
        }
        do {
            int gallopRightOffset = gallopRight(tmp[cursor2], arr, base1, len1, (len1 - 1), -1);
            count1 = (len1 - gallopRightOffset);
            if((count1 != 0)) {
                dest -= count1;
                cursor1 -= count1;
                len1 -= count1;
                copyArrToArr((cursor1 + 1), (dest + 1), count1);
                if((len1 == 0)) {
                    exitOuter = true;
                    break;
                }
            }
            writeValue(dest--, tmp[cursor2--]);
            len2--;
            if((len2 == 1)) {
                exitOuter = true;
                break;
            }
            int gallopLeftOffset = gallopLeft(arr[cursor1], tmp, 0, len2, (len2 - 1), cursor1);
            count2 = (len2 - gallopLeftOffset);
            if((count2 != 0)) {
                dest -= count2;
                cursor2 -= count2;
                len2 -= count2;
                copyTmpToArr((cursor2 + 1), (dest + 1), count2);
                if((len2 <= 1)) {
                    exitOuter = true;
                    break;
                }
            }
            writeValue(dest--, arr[cursor1--]);
            len1--;
            if((len1 == 0)) {
                exitOuter = true;
                break;
            }
            localMinGallop--;
        } while(((count1 >= MIN_GALLOP) || (count2 >= MIN_GALLOP)));
        if(exitOuter) {
            break;
        }
        if((localMinGallop < 0)) {
            localMinGallop = 0;
        }
        localMinGallop += 2;
    }
    minGallop = (((localMinGallop < 1)) ? (1) : (localMinGallop));
    metrics.finalMinGallop = minGallop;
    if((len2 == 1)) {
        dest -= len1;
        cursor1 -= len1;
        copyArrToArr((cursor1 + 1), (dest + 1), len1);
        writeValue(dest, tmp[cursor2]);
    } else {
        copyTmpToArr(0, (dest - (len2 - 1)), len2);
    }
}

void mergeAt(int index) {
    recordMetric("mergeAtCalls");
    int base1 = runBase[index];
    int len1 = runLen[index];
    int base2 = runBase[(index + 1)];
    int len2 = runLen[(index + 1)];
    runLen[index] = (len1 + len2);
    if((index == (stackSize - 3))) {
        runBase[(index + 1)] = runBase[(index + 2)];
        runLen[(index + 1)] = runLen[(index + 2)];
    }
    stackSize--;
    int k = gallopRight(arr[base2], arr, base1, len1, 0, base2);
    base1 += k;
    len1 -= k;
    if((len1 == 0)) {
        return;
    }
    len2 = gallopLeft(arr[((base1 + len1) - 1)], arr, base2, len2, (len2 - 1), ((base1 + len1) - 1));
    if((len2 == 0)) {
        return;
    }
    if((len1 <= len2)) {
        mergeLo(base1, len1, base2, len2);
    } else {
        mergeHi(base1, len1, base2, len2);
    }
}

void mergeCollapse() {
    while((stackSize > 1)) {
        int index = (stackSize - 2);
        if((((index > 0) && (runLen[(index - 1)] <= (runLen[index] + runLen[(index + 1)]))) || (((index - 1) > 0) && (runLen[(index - 2)] <= (runLen[(index - 1)] + runLen[index]))))) {
            if((runLen[(index - 1)] < runLen[(index + 1)])) {
                index--;
            }
            mergeAt(index);
        } else if((runLen[index] <= runLen[(index + 1)])) {
            mergeAt(index);
        } else {
            break;
        }
    }
}

void mergeForceCollapse() {
    while((stackSize > 1)) {
        int index = (stackSize - 2);
        if(((index > 0) && (runLen[(index - 1)] < runLen[(index + 1)]))) {
            index--;
        }
        mergeAt(index);
    }
}

public void Sort(int[] arr, int n, dynamic stats) {
    if((n < 2)) {
        return;
    }
    int MIN_MERGE = 32;
    int MIN_GALLOP = 7;
    int minGallop = MIN_GALLOP;
    int[] tmp = new int[(((n < (2 * MIN_MERGE))) ? ((n >>> 1)) : (256))];
    int tmpLen = n;
    int stackLen = (((n < 120)) ? (5) : ((((n < 1542)) ? (10) : ((((n < 119151)) ? (24) : (49))))));
    int[] runBase = new int[stackLen];
    int[] runLen = new int[stackLen];
    int stackSize = 0;
    int metrics = stats.educational.metrics;
    metrics.minMerge = MIN_MERGE;
    metrics.initialMinGallop = MIN_GALLOP;
    int lo = 0;
    int remaining = n;
    if((remaining < MIN_MERGE)) {
        int initRunLen = countRunAndMakeAscending(lo, n);
        binarySort(lo, n, (lo + initRunLen));
        checkpoint(n, n);
        for(int i=0; i<n; i++) {
            markSorted(i);
        }
        return;
    }
    int minRun = minRunLength(remaining);
    metrics.minRun = minRun;
    do {
        int currentRunLen = countRunAndMakeAscending(lo, n);
        if((currentRunLen < minRun)) {
            int forcedRunLen = (((remaining <= minRun)) ? (remaining) : (minRun));
            binarySort(lo, (lo + forcedRunLen), (lo + currentRunLen));
            currentRunLen = forcedRunLen;
            recordMetric("forcedRuns");
        }
        pushRun(lo, currentRunLen);
        mergeCollapse();
        lo += currentRunLen;
        remaining -= currentRunLen;
        checkpoint(lo, n);
    } while((remaining != 0));
    mergeForceCollapse();
    checkpoint(n, n);
    for(int i=0; i<n; i++) {
        markSorted(i);
    }
} #include <stdio.h>
#include <stdlib.h>
void recordMetric(int name, int );
int compareValues(int left, int right);
void writeValue(int index, int value);
void swapValues(int i, int j);
void copyArray(int src, int srcPos, int dest, int destPos, int length);
void copyTmpToArr(int tmpPos, int destPos, int length);
void copyArrToArr(int srcPos, int destPos, int length);
void reverseRange(int lo, int hi);
void binarySort(int lo, int hi, int start);
int countRunAndMakeAscending(int lo, int hi);
int minRunLength(int value);
void pushRun(int base, int length);
int gallopLeft(int key, int source, int base, int len, int hint, int keyIndex);
int gallopRight(int key, int source, int base, int len, int hint, int keyIndex);
void ensureCapacity(int minCapacity);
void mergeLo(int base1, int len1, int base2, int len2);
void mergeHi(int base1, int len1, int base2, int len2);
void mergeAt(int index);
void mergeCollapse();
void mergeForceCollapse();

void recordMetric(int name, int ) {
    metrics[name] = (((metrics[name]) != 0 ? (metrics[name]) : (0)) + delta);
}

int compareValues(int left, int right) {
    if((left < right)) {
        return -1;
    }
    if((left > right)) {
        return 1;
    }
    return 0;
}

void writeValue(int index, int value) {
    arr[index] = value;
    recordMetric("writeOperations");
    write(index, value);
}

void swapValues(int i, int j) {
    int value = arr[i];
    arr[i] = arr[j];
    arr[j] = value;
    recordMetric("pairSwaps");
    swap(i, j);
}

void copyArray(int src, int srcPos, int dest, int destPos, int length) {
    if((((src == dest) && (srcPos < destPos)) && ((srcPos + length) > destPos))) {
        for(int i=(length - 1); i>(0 - 1); i--) {
            dest[(destPos + i)] = src[(srcPos + i)];
        }
        return;
    }
    for(int i=0; i<length; i++) {
        dest[(destPos + i)] = src[(srcPos + i)];
    }
}

void copyTmpToArr(int tmpPos, int destPos, int length) {
    for(int i=0; i<length; i++) {
        writeValue((destPos + i), tmp[(tmpPos + i)]);
    }
}

void copyArrToArr(int srcPos, int destPos, int length) {
    if(((srcPos < destPos) && ((srcPos + length) > destPos))) {
        for(int i=(length - 1); i>(0 - 1); i--) {
            writeValue((destPos + i), arr[(srcPos + i)]);
        }
        return;
    }
    for(int i=0; i<length; i++) {
        writeValue((destPos + i), arr[(srcPos + i)]);
    }
}

void reverseRange(int lo, int hi) {
    hi--;
    while((lo < hi)) {
        swapValues(lo, hi);
        lo++;
        hi--;
    }
    recordMetric("reversedRuns");
}

void binarySort(int lo, int hi, int start) {
    if((start == lo)) {
        start++;
    }
    for(; (start < hi); start++) {
        int pivot = arr[start];
        int left = lo;
        int right = start;
        while((left < right)) {
            int mid = ((left + right) >>> 1);
            compare(start, mid);
            if((compareValues(pivot, arr[mid]) < 0)) {
                right = mid;
            } else {
                left = (mid + 1);
            }
        }
        for(int i=start; i>left; i--) {
            writeValue(i, arr[(i - 1)]);
        }
        writeValue(left, pivot);
        recordMetric("binaryInsertionPlacements");
    }
}

int countRunAndMakeAscending(int lo, int hi) {
    int runHi = (lo + 1);
    if((runHi == hi)) {
        return 1;
    }
    compare(runHi, lo);
    if((compareValues(arr[runHi], arr[lo]) < 0)) {
        runHi++;
        while((runHi < hi)) {
            compare(runHi, (runHi - 1));
            if(!(compareValues(arr[runHi], arr[(runHi - 1)]) < 0)) {
                break;
            }
            runHi++;
        }
        reverseRange(lo, runHi);
    } else {
        runHi++;
        while((runHi < hi)) {
            compare(runHi, (runHi - 1));
            if((compareValues(arr[runHi], arr[(runHi - 1)]) < 0)) {
                break;
            }
            runHi++;
        }
    }
    recordMetric("runsDetected");
    return (runHi - lo);
}

int minRunLength(int value) {
    int r = 0;
    while((value >= MIN_MERGE)) {
        r |= (value & 1);
        value >>= 1;
    }
    return (value + r);
}

void pushRun(int base, int length) {
    runBase[stackSize] = base;
    runLen[stackSize] = length;
    stackSize++;
    recordMetric("stackPushes");
}

int gallopLeft(int key, int source, int base, int len, int hint, int keyIndex) {
    recordMetric("gallopLeftCalls");
    int lastOfs = 0;
    int ofs = 1;
    if(((keyIndex >= 0) && (source == arr))) {
        compare(keyIndex, (base + hint));
    }
    if((compareValues(key, source[(base + hint)]) > 0)) {
        int maxOfs = (len - hint);
        while((ofs < maxOfs)) {
            if(((keyIndex >= 0) && (source == arr))) {
                compare(keyIndex, ((base + hint) + ofs));
            }
            if(!(compareValues(key, source[((base + hint) + ofs)]) > 0)) {
                break;
            }
            lastOfs = ofs;
            ofs = ((ofs << 1) + 1);
            if((ofs <= 0)) {
                ofs = maxOfs;
            }
        }
        if((ofs > maxOfs)) {
            ofs = maxOfs;
        }
        lastOfs += hint;
        ofs += hint;
    } else {
        int maxOfs = (hint + 1);
        while((ofs < maxOfs)) {
            if(((keyIndex >= 0) && (source == arr))) {
                compare(keyIndex, ((base + hint) - ofs));
            }
            if(!(compareValues(key, source[((base + hint) - ofs)]) <= 0)) {
                break;
            }
            lastOfs = ofs;
            ofs = ((ofs << 1) + 1);
            if((ofs <= 0)) {
                ofs = maxOfs;
            }
        }
        if((ofs > maxOfs)) {
            ofs = maxOfs;
        }
        int tmpOfs = lastOfs;
        lastOfs = (hint - ofs);
        ofs = (hint - tmpOfs);
    }
    lastOfs++;
    while((lastOfs < ofs)) {
        int mid = (lastOfs + ((ofs - lastOfs) >>> 1));
        if(((keyIndex >= 0) && (source == arr))) {
            compare(keyIndex, (base + mid));
        }
        if((compareValues(key, source[(base + mid)]) > 0)) {
            lastOfs = (mid + 1);
        } else {
            ofs = mid;
        }
    }
    return ofs;
}

int gallopRight(int key, int source, int base, int len, int hint, int keyIndex) {
    recordMetric("gallopRightCalls");
    int lastOfs = 0;
    int ofs = 1;
    if(((keyIndex >= 0) && (source == arr))) {
        compare(keyIndex, (base + hint));
    }
    if((compareValues(key, source[(base + hint)]) < 0)) {
        int maxOfs = (hint + 1);
        while((ofs < maxOfs)) {
            if(((keyIndex >= 0) && (source == arr))) {
                compare(keyIndex, ((base + hint) - ofs));
            }
            if(!(compareValues(key, source[((base + hint) - ofs)]) < 0)) {
                break;
            }
            lastOfs = ofs;
            ofs = ((ofs << 1) + 1);
            if((ofs <= 0)) {
                ofs = maxOfs;
            }
        }
        if((ofs > maxOfs)) {
            ofs = maxOfs;
        }
        int tmpOfs = lastOfs;
        lastOfs = (hint - ofs);
        ofs = (hint - tmpOfs);
    } else {
        int maxOfs = (len - hint);
        while((ofs < maxOfs)) {
            if(((keyIndex >= 0) && (source == arr))) {
                compare(keyIndex, ((base + hint) + ofs));
            }
            if(!(compareValues(key, source[((base + hint) + ofs)]) >= 0)) {
                break;
            }
            lastOfs = ofs;
            ofs = ((ofs << 1) + 1);
            if((ofs <= 0)) {
                ofs = maxOfs;
            }
        }
        if((ofs > maxOfs)) {
            ofs = maxOfs;
        }
        lastOfs += hint;
        ofs += hint;
    }
    lastOfs++;
    while((lastOfs < ofs)) {
        int mid = (lastOfs + ((ofs - lastOfs) >>> 1));
        if(((keyIndex >= 0) && (source == arr))) {
            compare(keyIndex, (base + mid));
        }
        if((compareValues(key, source[(base + mid)]) < 0)) {
            ofs = mid;
        } else {
            lastOfs = (mid + 1);
        }
    }
    return ofs;
}

void ensureCapacity(int minCapacity) {
    if((tmpLen >= minCapacity)) {
        return;
    }
    int newSize = minCapacity;
    newSize |= (newSize >> 1);
    newSize |= (newSize >> 2);
    newSize |= (newSize >> 4);
    newSize |= (newSize >> 8);
    newSize |= (newSize >> 16);
    newSize++;
    if((newSize < 0)) {
        newSize = minCapacity;
    } else {
        newSize = ((minCapacity) > (((newSize) < ((n >>> 1)) ? (newSize) : ((n >>> 1)))) ? (minCapacity) : (((newSize) < ((n >>> 1)) ? (newSize) : ((n >>> 1)))));
    }
    tmp = _new_arr_newSize;
    tmpLen = newSize;
    recordMetric("tmpResizes");
}

void mergeLo(int base1, int len1, int base2, int len2) {
    recordMetric("mergeLoCalls");
    ensureCapacity(len1);
    copyArray(arr, base1, tmp, 0, len1);
    int cursor1 = 0;
    int cursor2 = base2;
    int dest = base1;
    writeValue(dest++, arr[cursor2++]);
    len2--;
    if((len2 == 0)) {
        copyTmpToArr(cursor1, dest, len1);
        return;
    }
    if((len1 == 1)) {
        copyArrToArr(cursor2, dest, len2);
        writeValue((dest + len2), tmp[cursor1]);
        return;
    }
    int localMinGallop = minGallop;
    while(1) {
        int count1 = 0;
        int count2 = 0;
        int exitOuter = 0;
        do {
            if((compareValues(arr[cursor2], tmp[cursor1]) < 0)) {
                writeValue(dest++, arr[cursor2++]);
                count2++;
                count1 = 0;
                len2--;
                if((len2 == 0)) {
                    exitOuter = 1;
                    break;
                }
            } else {
                writeValue(dest++, tmp[cursor1++]);
                count1++;
                count2 = 0;
                len1--;
                if((len1 == 1)) {
                    exitOuter = 1;
                    break;
                }
            }
        } while(((count1 | count2) < localMinGallop));
        if(exitOuter) {
            break;
        }
        do {
            count1 = gallopRight(arr[cursor2], tmp, cursor1, len1, 0, cursor2);
            if((count1 != 0)) {
                copyTmpToArr(cursor1, dest, count1);
                dest += count1;
                cursor1 += count1;
                len1 -= count1;
                if((len1 <= 1)) {
                    exitOuter = 1;
                    break;
                }
            }
            writeValue(dest++, arr[cursor2++]);
            len2--;
            if((len2 == 0)) {
                exitOuter = 1;
                break;
            }
            count2 = gallopLeft(tmp[cursor1], arr, cursor2, len2, 0, -1);
            if((count2 != 0)) {
                copyArrToArr(cursor2, dest, count2);
                dest += count2;
                cursor2 += count2;
                len2 -= count2;
                if((len2 == 0)) {
                    exitOuter = 1;
                    break;
                }
            }
            writeValue(dest++, tmp[cursor1++]);
            len1--;
            if((len1 == 1)) {
                exitOuter = 1;
                break;
            }
            localMinGallop--;
        } while(((count1 >= MIN_GALLOP) || (count2 >= MIN_GALLOP)));
        if(exitOuter) {
            break;
        }
        if((localMinGallop < 0)) {
            localMinGallop = 0;
        }
        localMinGallop += 2;
    }
    minGallop = (((localMinGallop < 1)) ? (1) : (localMinGallop));
    metrics.finalMinGallop = minGallop;
    if((len1 == 1)) {
        copyArrToArr(cursor2, dest, len2);
        writeValue((dest + len2), tmp[cursor1]);
    } else {
        copyTmpToArr(cursor1, dest, len1);
    }
}

void mergeHi(int base1, int len1, int base2, int len2) {
    recordMetric("mergeHiCalls");
    ensureCapacity(len2);
    copyArray(arr, base2, tmp, 0, len2);
    int cursor1 = ((base1 + len1) - 1);
    int cursor2 = (len2 - 1);
    int dest = ((base2 + len2) - 1);
    writeValue(dest--, arr[cursor1--]);
    len1--;
    if((len1 == 0)) {
        copyTmpToArr(0, (dest - (len2 - 1)), len2);
        return;
    }
    if((len2 == 1)) {
        dest -= len1;
        cursor1 -= len1;
        copyArrToArr((cursor1 + 1), (dest + 1), len1);
        writeValue(dest, tmp[cursor2]);
        return;
    }
    int localMinGallop = minGallop;
    while(1) {
        int count1 = 0;
        int count2 = 0;
        int exitOuter = 0;
        do {
            if((compareValues(tmp[cursor2], arr[cursor1]) < 0)) {
                writeValue(dest--, arr[cursor1--]);
                count1++;
                count2 = 0;
                len1--;
                if((len1 == 0)) {
                    exitOuter = 1;
                    break;
                }
            } else {
                writeValue(dest--, tmp[cursor2--]);
                count2++;
                count1 = 0;
                len2--;
                if((len2 == 1)) {
                    exitOuter = 1;
                    break;
                }
            }
        } while(((count1 | count2) < localMinGallop));
        if(exitOuter) {
            break;
        }
        do {
            int gallopRightOffset = gallopRight(tmp[cursor2], arr, base1, len1, (len1 - 1), -1);
            count1 = (len1 - gallopRightOffset);
            if((count1 != 0)) {
                dest -= count1;
                cursor1 -= count1;
                len1 -= count1;
                copyArrToArr((cursor1 + 1), (dest + 1), count1);
                if((len1 == 0)) {
                    exitOuter = 1;
                    break;
                }
            }
            writeValue(dest--, tmp[cursor2--]);
            len2--;
            if((len2 == 1)) {
                exitOuter = 1;
                break;
            }
            int gallopLeftOffset = gallopLeft(arr[cursor1], tmp, 0, len2, (len2 - 1), cursor1);
            count2 = (len2 - gallopLeftOffset);
            if((count2 != 0)) {
                dest -= count2;
                cursor2 -= count2;
                len2 -= count2;
                copyTmpToArr((cursor2 + 1), (dest + 1), count2);
                if((len2 <= 1)) {
                    exitOuter = 1;
                    break;
                }
            }
            writeValue(dest--, arr[cursor1--]);
            len1--;
            if((len1 == 0)) {
                exitOuter = 1;
                break;
            }
            localMinGallop--;
        } while(((count1 >= MIN_GALLOP) || (count2 >= MIN_GALLOP)));
        if(exitOuter) {
            break;
        }
        if((localMinGallop < 0)) {
            localMinGallop = 0;
        }
        localMinGallop += 2;
    }
    minGallop = (((localMinGallop < 1)) ? (1) : (localMinGallop));
    metrics.finalMinGallop = minGallop;
    if((len2 == 1)) {
        dest -= len1;
        cursor1 -= len1;
        copyArrToArr((cursor1 + 1), (dest + 1), len1);
        writeValue(dest, tmp[cursor2]);
    } else {
        copyTmpToArr(0, (dest - (len2 - 1)), len2);
    }
}

void mergeAt(int index) {
    recordMetric("mergeAtCalls");
    int base1 = runBase[index];
    int len1 = runLen[index];
    int base2 = runBase[(index + 1)];
    int len2 = runLen[(index + 1)];
    runLen[index] = (len1 + len2);
    if((index == (stackSize - 3))) {
        runBase[(index + 1)] = runBase[(index + 2)];
        runLen[(index + 1)] = runLen[(index + 2)];
    }
    stackSize--;
    int k = gallopRight(arr[base2], arr, base1, len1, 0, base2);
    base1 += k;
    len1 -= k;
    if((len1 == 0)) {
        return;
    }
    len2 = gallopLeft(arr[((base1 + len1) - 1)], arr, base2, len2, (len2 - 1), ((base1 + len1) - 1));
    if((len2 == 0)) {
        return;
    }
    if((len1 <= len2)) {
        mergeLo(base1, len1, base2, len2);
    } else {
        mergeHi(base1, len1, base2, len2);
    }
}

void mergeCollapse() {
    while((stackSize > 1)) {
        int index = (stackSize - 2);
        if((((index > 0) && (runLen[(index - 1)] <= (runLen[index] + runLen[(index + 1)]))) || (((index - 1) > 0) && (runLen[(index - 2)] <= (runLen[(index - 1)] + runLen[index]))))) {
            if((runLen[(index - 1)] < runLen[(index + 1)])) {
                index--;
            }
            mergeAt(index);
        } else if((runLen[index] <= runLen[(index + 1)])) {
            mergeAt(index);
        } else {
            break;
        }
    }
}

void mergeForceCollapse() {
    while((stackSize > 1)) {
        int index = (stackSize - 2);
        if(((index > 0) && (runLen[(index - 1)] < runLen[(index + 1)]))) {
            index--;
        }
        mergeAt(index);
    }
}

void sort(int arr[], int n, int* comparisons, int* swaps) {
    if((n < 2)) {
        return;
    }
    int MIN_MERGE = 32;
    int MIN_GALLOP = 7;
    int minGallop = MIN_GALLOP;
    int* tmp = (int*)malloc(((((n < (2 * MIN_MERGE))) ? ((n >>> 1)) : (256))) * sizeof(int));
    int tmpLen = n;
    int stackLen = (((n < 120)) ? (5) : ((((n < 1542)) ? (10) : ((((n < 119151)) ? (24) : (49))))));
    int* runBase = (int*)malloc((stackLen) * sizeof(int));
    int* runLen = (int*)malloc((stackLen) * sizeof(int));
    int stackSize = 0;
    int metrics = (*educational).metrics;
    metrics.minMerge = MIN_MERGE;
    metrics.initialMinGallop = MIN_GALLOP;
    int lo = 0;
    int remaining = n;
    if((remaining < MIN_MERGE)) {
        int initRunLen = countRunAndMakeAscending(lo, n);
        binarySort(lo, n, (lo + initRunLen));
        checkpoint(n, n);
        for(int i=0; i<n; i++) {
            markSorted(i);
        }
        return;
    }
    int minRun = minRunLength(remaining);
    metrics.minRun = minRun;
    do {
        int currentRunLen = countRunAndMakeAscending(lo, n);
        if((currentRunLen < minRun)) {
            int forcedRunLen = (((remaining <= minRun)) ? (remaining) : (minRun));
            binarySort(lo, (lo + forcedRunLen), (lo + currentRunLen));
            currentRunLen = forcedRunLen;
            recordMetric("forcedRuns");
        }
        pushRun(lo, currentRunLen);
        mergeCollapse();
        lo += currentRunLen;
        remaining -= currentRunLen;
        checkpoint(lo, n);
    } while((remaining != 0));
    mergeForceCollapse();
    checkpoint(n, n);
    for(int i=0; i<n; i++) {
        markSorted(i);
    }
} 