Simon Tatham's linked list merge sort algorithm http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html
510657
function sortLinked(list) {
        var i, p, q, e, tail, numMerges, pSize, qSize, inSize = 1;
        do {
            p = list;
            list = null;
            tail = null;
            numMerges = 0;
            while (p) {
                numMerges++;
                q = p;
                pSize = 0;
                for (i = 0; i < inSize; i++) {
                    pSize++;
                    q = q.nextZ;
                    if (!q)
                        break;
                }
                qSize = inSize;
                while (pSize > 0 || (qSize > 0 && q)) {
                    if (pSize === 0) {
                        e = q;
                        q = q.nextZ;
                        qSize--;
                    }
                    else if (qSize === 0 || !q) {
                        e = p;
                        p = p.nextZ;
                        pSize--;
                    }
                    else if (p.z <= q.z) {
                        e = p;
                        p = p.nextZ;
                        pSize--;
                    }
                    else {
                        e = q;
                        q = q.nextZ;
                        qSize--;
                    }
                    if (tail)
                        tail.nextZ = e;
                    else
                        list = e;
                    e.prevZ = tail;
                    tail = e;
                }
                p = q;
            }
            tail.nextZ = null;
            inSize *= 2;
        } while (numMerges > 1);
        return list;
    }
983882
private void mainQSort3(final BZip2CompressorOutputStream.Data dataShadow,
                            final int loSt, final int hiSt, final int dSt,
                            final int last) {
        final int[] stack_ll = this.stack_ll;
        final int[] stack_hh = this.stack_hh;
        final int[] stack_dd = this.stack_dd;
        final int[] fmap = dataShadow.fmap;
        final byte[] block = dataShadow.block;

        stack_ll[0] = loSt;
        stack_hh[0] = hiSt;
        stack_dd[0] = dSt;

        for (int sp = 1; --sp >= 0;) {
            final int lo = stack_ll[sp];
            final int hi = stack_hh[sp];
            final int d = stack_dd[sp];

            if ((hi - lo < SMALL_THRESH) || (d > DEPTH_THRESH)) {
                if (mainSimpleSort(dataShadow, lo, hi, d, last)) {
                    return;
                }
            } else {
                final int d1 = d + 1;
                final int med = med3(block[fmap[lo] + d1],
                                     block[fmap[hi] + d1], block[fmap[(lo + hi) >>> 1] + d1]) & 0xff;

                int unLo = lo;
                int unHi = hi;
                int ltLo = lo;
                int gtHi = hi;

                while (true) {
                    while (unLo <= unHi) {
                        final int n = (block[fmap[unLo] + d1] & 0xff)
                            - med;
                        if (n == 0) {
                            final int temp = fmap[unLo];
                            fmap[unLo++] = fmap[ltLo];
                            fmap[ltLo++] = temp;
                        } else if (n < 0) {
                            unLo++;
                        } else {
                            break;
                        }
                    }

                    while (unLo <= unHi) {
                        final int n = (block[fmap[unHi] + d1] & 0xff)
                            - med;
                        if (n == 0) {
                            final int temp = fmap[unHi];
                            fmap[unHi--] = fmap[gtHi];
                            fmap[gtHi--] = temp;
                        } else if (n > 0) {
                            unHi--;
                        } else {
                            break;
                        }
                    }

                    if (unLo <= unHi) {
                        final int temp = fmap[unLo];
                        fmap[unLo++] = fmap[unHi];
                        fmap[unHi--] = temp;
                    } else {
                        break;
                    }
                }

                if (gtHi < ltLo) {
                    stack_ll[sp] = lo;
                    stack_hh[sp] = hi;
                    stack_dd[sp] = d1;
                    sp++;
                } else {
                    int n = ((ltLo - lo) < (unLo - ltLo)) ? (ltLo - lo)
                        : (unLo - ltLo);
                    vswap(fmap, lo, unLo - n, n);
                    int m = ((hi - gtHi) < (gtHi - unHi)) ? (hi - gtHi)
                        : (gtHi - unHi);
                    vswap(fmap, unLo, hi - m + 1, m);

                    n = lo + unLo - ltLo - 1;
                    m = hi - (gtHi - unHi) + 1;

                    stack_ll[sp] = lo;
                    stack_hh[sp] = n;
                    stack_dd[sp] = d;
                    sp++;

                    stack_ll[sp] = n + 1;
                    stack_hh[sp] = m - 1;
                    stack_dd[sp] = d1;
                    sp++;

                    stack_ll[sp] = m;
                    stack_hh[sp] = hi;
                    stack_dd[sp] = d;
                    sp++;
                }
            }
        }
    }
849503
public List<PlanNode> findAllAtOrBelow( Traversal order ) {
        assert order != null;
        LinkedList<PlanNode> results = new LinkedList<PlanNode>();
        LinkedList<PlanNode> queue = new LinkedList<PlanNode>();
        queue.add(this);
        while (!queue.isEmpty()) {
            PlanNode aNode = queue.poll();
            switch (order) {
                case LEVEL_ORDER:
                    results.add(aNode);
                    queue.addAll(aNode.getChildren());
                    break;
                case PRE_ORDER:
                    results.add(aNode);
                    queue.addAll(0, aNode.getChildren());
                    break;
                case POST_ORDER:
                    queue.addAll(0, aNode.getChildren());
                    results.addFirst(aNode);
                    break;
            }
        }
        return results;
    }
893788
public void shuttlesort(int from[], int to[], int low, int high) {
        if (high - low < 2) {
            return;
        }
        int middle = (low + high) / 2;
        shuttlesort(to, from, low, middle);
        shuttlesort(to, from, middle, high);

        int p = low;
        int q = middle;

        /* This is an optional short-cut; at each recursive call,
        check to see if the elements in this subset are already
        ordered.  If so, no further comparisons are needed; the
        sub-array can just be copied.  The array must be copied rather
        than assigned otherwise sister calls in the recursion might
        get out of sync.  When the number of elements is three they
        are partitioned so that the first set, [low, mid), has one
        element and and the second, [mid, high), has two. We skip the
        optimisation when the number of elements is three or less as
        the first compare in the normal merge will produce the same
        sequence of steps. This optimisation seems to be worthwhile
        for partially ordered lists but some analysis is needed to
        find out how the performance drops to Nlog(N) as the initial
        order diminishes - it may drop very quickly.  */

        if (high - low >= 4 && compare(from[middle - 1], from[middle]) <= 0) {
            System.arraycopy(from, low, to, low, high - low);
            return;
        }

        // A normal merge.

        for (int i = low; i < high; i++) {
            if (q >= high || (p < middle && compare(from[p], from[q]) <= 0)) {
                to[i] = from[p++];
            } else {
                to[i] = from[q++];
            }
        }
    }
514697
private static <V> Collection<V> sorted(Iterable<V> source, Comparator<V> comparator, int size)
    {
        V[] vs = (V[]) new Object[size];
        int i = 0;
        for (V v : source)
            vs[i++] = v;
        Arrays.sort(vs, comparator);
        return Arrays.asList(vs);
    }
255835
public static <K, V> LinkedHashMap<K, V> sortToMap(Collection<Map.Entry<K, V>> entryCollection, Comparator<Map.Entry<K, V>> comparator) {
		List<Map.Entry<K, V>> list = new LinkedList<>(entryCollection);
		Collections.sort(list, comparator);

		LinkedHashMap<K, V> result = new LinkedHashMap<>();
		for (Map.Entry<K, V> entry : list) {
			result.put(entry.getKey(), entry.getValue());
		}
		return result;
	}
193064
@SuppressWarnings("InnerAssignment")
    private void quickSort(PagesIndex pagesIndex, int from, int to)
    {
        int len = to - from;
        // Insertion sort on smallest arrays
        if (len < SMALL) {
            for (int i = from; i < to; i++) {
                for (int j = i; j > from && (comparator.compareTo(pagesIndex, j - 1, j) > 0); j--) {
                    pagesIndex.swap(j, j - 1);
                }
            }
            return;
        }

        // Choose a partition element, v
        int m = from + len / 2; // Small arrays, middle element
        if (len > SMALL) {
            int l = from;
            int n = to - 1;
            if (len > MEDIUM) { // Big arrays, pseudomedian of 9
                int s = len / 8;
                l = median3(pagesIndex, l, l + s, l + 2 * s);
                m = median3(pagesIndex, m - s, m, m + s);
                n = median3(pagesIndex, n - 2 * s, n - s, n);
            }
            m = median3(pagesIndex, l, m, n); // Mid-size, med of 3
        }
        // int v = x[m];

        int a = from;
        int b = a;
        int c = to - 1;
        // Establish Invariant: v* (<v)* (>v)* v*
        int d = c;
        while (true) {
            int comparison;
            while (b <= c && ((comparison = comparator.compareTo(pagesIndex, b, m)) <= 0)) {
                if (comparison == 0) {
                    if (a == m) {
                        m = b; // moving target; DELTA to JDK !!!
                    }
                    else if (b == m) {
                        m = a; // moving target; DELTA to JDK !!!
                    }
                    pagesIndex.swap(a++, b);
                }
                b++;
            }
            while (c >= b && ((comparison = comparator.compareTo(pagesIndex, c, m)) >= 0)) {
                if (comparison == 0) {
                    if (c == m) {
                        m = d; // moving target; DELTA to JDK !!!
                    }
                    else if (d == m) {
                        m = c; // moving target; DELTA to JDK !!!
                    }
                    pagesIndex.swap(c, d--);
                }
                c--;
            }
            if (b > c) {
                break;
            }
            if (b == m) {
                m = d; // moving target; DELTA to JDK !!!
            }
            else if (c == m) {
                m = c; // moving target; DELTA to JDK !!!
            }
            pagesIndex.swap(b++, c--);
        }

        // Swap partition elements back to middle
        int s;
        int n = to;
        s = Math.min(a - from, b - a);
        vectorSwap(pagesIndex, from, b - s, s);
        s = Math.min(d - c, n - d - 1);
        vectorSwap(pagesIndex, b, n - s, s);

        // Recursively sort non-partition-elements
        if ((s = b - a) > 1) {
            quickSort(pagesIndex, from, from + s);
        }
        if ((s = d - c) > 1) {
            quickSort(pagesIndex, n - s, n);
        }
    }
907605
public RawKeyValueIterator sort() {
    MergeSort m = new MergeSort(this);
    int count = super.count;
    if (count == 0) return null;
    int [] pointers = super.pointers;
    int [] pointersCopy = new int[count];
    System.arraycopy(pointers, 0, pointersCopy, 0, count);
    m.mergeSort(pointers, pointersCopy, 0, count);
    return new MRSortResultIterator(super.keyValBuffer, pointersCopy, 
                                    super.startOffsets, super.keyLengths, super.valueLengths);
  }
690017
def _argsort_and_resolve_ties(time, random_state):
        """"""
        n_samples = len(time)
        order = numpy.argsort(time, kind="mergesort")

        i = 0
        while i < n_samples - 1:
            inext = i + 1
            while inext < n_samples and time[order[i]] == time[order[inext]]:
                inext += 1

            if i + 1 != inext:
                # resolve ties randomly
                random_state.shuffle(order[i:inext])
            i = inext
        return order
4103
public static <E extends Comparable<E>> void sort(List<E> list) {
        Merge.sort(list, 0, list.size()-1, false);
    }
987081
private IntIntPair[] sortEdges(int[] dindex) {
    IntIntPair[] edgesort = new IntIntPair[shared.layout.edges.size()];
    int e = 0;
    for(Layout.Edge edge : shared.layout.edges) {
      int i1 = dindex[edge.dim1], i2 = dindex[edge.dim2];
      edgesort[e] = new IntIntPair(Math.min(i1, i2), e);
      e++;
    }
    Arrays.sort(edgesort);
    return edgesort;
  }
1259956
private static <T extends Comparable<? super T>> void sort(T[] a, int n) {
        int inc = 1;
        do {
            inc *= 3;
            inc++;
        } while (inc <= n);

        do {
            inc /= 3;
            for (int i = inc; i < n; i++) {
                T v = a[i];
                int j = i;
                while (a[j - inc].compareTo(v) < 0) {
                    a[j] = a[j - inc];
                    j -= inc;
                    if (j < inc) {
                        break;
                    }
                }
                a[j] = v;
            }
        } while (inc > 1);
    }
419146
private void topologicalSortVisit(V n, List<V> L, Set<V> visited, LinkedHashSet<V> sequence) throws CycleException, EX {
		//    if n has not been visited yet then
		//        mark n as visited
		if(visited.add(n)) {
			//        for each node m with an edge from n to m do
			for(Edge<V> e : (isForward ? graph.getEdgesFrom(n) : graph.getEdgesTo(n))) {
				V m = isForward ? e.getTo() : e.getFrom();
				//            visit(m)
				if(!sequence.add(m)) {
					List<V> vertices = new ArrayList<>();
					boolean found = false;
					for(V seq : sequence) {
						if(!found && seq.equals(m)) found = true;
						if(found) vertices.add(seq);
					}
					vertices.add(m);
					throw new CycleException(AoCollections.optimalUnmodifiableList(vertices));
				}
				topologicalSortVisit(m, L, visited, sequence);
				sequence.remove(m);
			}
			//        add n to L
			L.add(n);
		}
	}
1254070
def get_itemstr_list(list_, **listkw):
    
    import utool as ut
    _valstr = _make_valstr(**listkw)

    def make_item_str(item):
        item_str = _valstr(item)
        return item_str

    items = list(list_)
    itemstr_list = [make_item_str(item) for item in items]

    dosort = listkw.get('sorted_', None)
    if dosort is None:
        # Force orderings on sets.
        dosort = isinstance(list_, (set, frozenset))
    if dosort:
        # First try to sort items by their normal values
        # If that doesnt work, then sort by their string values
        try:
            # Set ordering is not unique. Sort by strings values instead.
            if _peek_isinstance(items, (set, frozenset)):
                raise Exception
            sortx = ut.argsort2(items)
        except Exception:
            sortx = ut.argsort2(itemstr_list)
        itemstr_list = ut.take(itemstr_list, sortx)
    return itemstr_list
868905
function sortNodesByDepth (graph) {
      // Build the map of nodes to their levels
      let nodesSortedByDepth = [];
      let index;
      for (index in graph.nodes) {
        if ({}.hasOwnProperty.call(graph.nodes, index)) {
          const node = graph.nodes[index];
          nodesSortedByDepth[node.rank] = nodesSortedByDepth[node.rank] || [];
          nodesSortedByDepth[node.rank].push(node);
        }
      }

      // Remove empty ranks (and normalize to base 0)
      nodesSortedByDepth = nodesSortedByDepth.reduce((a, n) => { a.push(n); return a; }, []);

      const maxNodesPerDepth = 30;
      for (let i = 0; i < nodesSortedByDepth.length; i++) {
        const nodesInDepth = nodesSortedByDepth[i];
        if (nodesInDepth.length > maxNodesPerDepth) {
          const nodesToKeep = Math.min((nodesInDepth.length / 2) - 1, maxNodesPerDepth);
          const newNodeDepth = nodesInDepth.splice(nodesToKeep);
          nodesSortedByDepth.splice(i + 1, 0, newNodeDepth);
        }
      }

      return nodesSortedByDepth;
    }
714193
private void ssMergeForward(int PA, int first, int middle, int last, int buf,
                                int depth) {
        // PA, first, middle, last, buf are pointers to SA
        int a, b, c, bufend;// pointers to SA
        int t, r;

        bufend = buf + (middle - first) - 1;
        ssBlockSwap(buf, first, middle - first);

        for (t = SA[a = first], b = buf, c = middle; ; ) {
            r = ssCompare(PA + SA[b], PA + SA[c], depth);
            if (r < 0) {
                do {
                    SA[a++] = SA[b];
                    if (bufend <= b) {
                        SA[bufend] = t;
                        return;
                    }
                    SA[b++] = SA[a];
                }
                while (SA[b] < 0);
            } else if (r > 0) {
                do {
                    SA[a++] = SA[c];
                    SA[c++] = SA[a];
                    if (last <= c) {
                        while (b < bufend) {
                            SA[a++] = SA[b];
                            SA[b++] = SA[a];
                        }
                        SA[a] = SA[b];
                        SA[b] = t;
                        return;
                    }
                }
                while (SA[c] < 0);
            } else {
                SA[c] = ~SA[c];
                do {
                    SA[a++] = SA[b];
                    if (bufend <= b) {
                        SA[bufend] = t;
                        return;
                    }
                    SA[b++] = SA[a];
                }
                while (SA[b] < 0);

                do {
                    SA[a++] = SA[c];
                    SA[c++] = SA[a];
                    if (last <= c) {
                        while (b < bufend) {
                            SA[a++] = SA[b];
                            SA[b++] = SA[a];
                        }
                        SA[a] = SA[b];
                        SA[b] = t;
                        return;
                    }
                }
                while (SA[c] < 0);
            }
        }

    }
807383
public static <T extends Comparable<? super T>, L extends List<T>> L sortThis(L list)
    {
        if (list instanceof MutableList<?>)
        {
            ((MutableList<T>) list).sortThis();
        }
        else if (list instanceof ArrayList)
        {
            ArrayListIterate.sortThis((ArrayList<T>) list);
        }
        else
        {
            if (list.size() > 1)
            {
                Collections.sort(list);
            }
        }
        return list;
    }