Bucket Sort
        Complexity: O(n^2)
        The complexity is dominated by nextSort
971648
def bucket_sort(arr):
    ''' 
    '''
    # The number of buckets and make buckets
    num_buckets = len(arr)
    buckets = [[] for bucket in range(num_buckets)]
    # Assign values into bucket_sort
    for value in arr:
        index = value * num_buckets // (max(arr) + 1)
        buckets[index].append(value)
    # Sort
    sorted_list = []
    for i in range(num_buckets):
        sorted_list.extend(next_sort(buckets[i]))
    return sorted_list
887602
private int bucketIndexFor(final int value) {
    if (value < cutoff) {
      return value / interval;
    }
    int bucket = num_linear_buckets  // Skip all linear buckets.
      // And find which bucket the rest (after `cutoff') should be in.
      // Reminder: the first exponential bucket ends at 2^exp_bucket_shift.
      + log2rounddown((value - cutoff) >> exp_bucket_shift);
    if (bucket >= buckets.length) {
      return buckets.length - 1;
    }
    return bucket;
  }
1083085
private int rankPermutationLexicographically(int[] permutation) {
        int rank = 0;
        int n = permutation.length;
        int[] counter = new int[n + 1];
        for (int i = 1; i < permutation.length; i++) {
            counter[i] = permutation[i - 1] + 1;
        }
        for (int j = 1; j <= n; j++) {
            rank += (counter[j] - 1) * factorial(n - j);
            for (int i = j + 1; i <= n; i++) {
                if (counter[i] > counter[j]) {
                    counter[i]--;
                }
            }
        }
        return rank + 1;
    }
1330978
def operator_complexity(self):
        
        return sum([level.A.nnz for level in self.levels]) /\
            float(self.levels[0].A.nnz)
926501
private static int sortAbstractLongArray(Block array, long[] buffer, AbstractType type)
    {
        int arraySize = array.getPositionCount();
        int nonNullSize = 0;
        for (int i = 0; i < arraySize; i++) {
            if (!array.isNull(i)) {
                buffer[nonNullSize++] = type.getLong(array, i);
            }
        }
        for (int i = 1; i < nonNullSize; i++) {
            if (buffer[i - 1] > buffer[i]) {
                Arrays.sort(buffer, 0, nonNullSize);
                break;
            }
        }
        return nonNullSize;
    }
103302
function(T, SA, fs, n, k, isbwt) {
        var C, B, RA;
        var i, j, b, c, m, p, q, name, pidx = 0, newfs;
        var c0, c1;
        var flags = 0;

        // allocate temporary storage [CSA]
        if (k <= 256) {
            C = Util.makeS32Buffer(k);
            if (k <= fs) { B = SA.subarray(n + fs - k); flags = 1; }
            else { B = Util.makeS32Buffer(k); flags = 3; }
        } else if (k <= fs) {
            C = SA.subarray(n + fs - k);
            if (k <= (fs - k)) { B = SA.subarray(n + fs - k * 2); flags = 0; }
            else if (k <= 1024) { B = Util.makeS32Buffer(k); flags = 2; }
            else { B = C; flags = 8; }
        } else {
            C = B = Util.makeS32Buffer(k);
            flags = 4 | 8;
        }

        /* stage 1: reduce the problem by at least 1/2
           sort all the LMS-substrings */
        getCounts(T, C, n, k);
        getBuckets(C, B, k, true); /* find ends of buckets */
        for (i = 0; i < n; i++) { SA[i] = 0; }
        b = -1; i = n - 1; j = n; m = 0; c0 = T[n - 1];
        do { c1 = c0; } while ((--i >= 0) && ((c0 = T[i]) >= c1));
        for (; i >= 0 ;) {
            do { c1 = c0; } while ((--i >= 0) && ((c0 = T[i]) <= c1));
            if ( i >= 0 ) {
                if ( b >= 0 ) { SA[b] = j; }
                b = --B[c1];
                j = i;
                ++m;
                do { c1 = c0; } while ((--i >= 0) && ((c0 = T[i]) >= c1));
            }
        }

        if (m > 1) {
            LMSsort(T, SA, C, B, n, k);
            name = LMSpostproc(T, SA, n, m);
        } else if (m === 1) {
            SA[b] = j + 1;
            name = 1;
        } else {
            name = 0;
        }

        /* stage 2: solve the reduced problem
           recurse if names are not yet unique */
        if(name < m) {
            if((flags & 4) !== 0) { C = null; B = null; }
            if((flags & 2) !== 0) { B = null; }
            newfs = (n + fs) - (m * 2);
            if((flags & (1 | 4 | 8)) === 0) {
                if((k + name) <= newfs) { newfs -= k; }
                else { flags |= 8; }
            }
            ASSERT( (n >>> 1) <= (newfs + m) );
            for (i = m + (n >>> 1) - 1, j = m * 2 + newfs - 1; m <= i; i--) {
                if(SA[i] !== 0) { SA[j--] = SA[i] - 1; }
            }
            RA = SA.subarray(m + newfs);
            SA_IS(RA, SA, newfs, m, name, false);
            RA = null;

            i = n - 1; j = m * 2 - 1; c0 = T[n - 1];
            do { c1 = c0; } while ((--i >= 0) && ((c0 = T[i]) >= c1));
            for (; i >= 0 ;) {
                do { c1 = c0; } while ((--i >= 0) && ((c0 = T[i]) <= c1));
                if ( i >= 0 ) {
                    SA[j--] = i + 1;
                    do { c1 = c0; } while ((--i >= 0) && ((c0 = T[i]) >= c1));
                }
            }

            for (i = 0; i < m; i++) { SA[i] = SA[m + SA[i]]; }
            if((flags & 4) !== 0) { C = B = Util.makeS32Buffer(k); }
            if((flags & 2) !== 0) { B = Util.makeS32Buffer(k); }
        }

        /* stage 3: induce the result for the original problem */
        if((flags & 8) !== 0) { getCounts(T, C, n, k); }
        /* put all left-most S characters into their buckets */
        if (m > 1) {
            getBuckets(C, B, k, true); /* find ends of buckets */
            i = m - 1; j = n; p = SA[m - 1]; c1 = T[p];
            do {
                q = B[c0 = c1];
                while (q < j) { SA[--j] = 0; }
                do {
                    SA[--j] = p;
                    if(--i < 0) { break; }
                    p = SA[i];
                } while((c1 = T[p]) === c0);
            } while (i >= 0 );
            while ( j > 0 ) { SA[--j] = 0; }
        }
        if (!isbwt) { induceSA(T, SA, C, B, n, k); }
        else { pidx = computeBWT(T, SA, C, B, n, k); }
        C = null; B = null;
        return pidx;
    }
197024
def top_sort_recursive(graph):
    
    order, enter, state = [], set(graph), {}
    
    def dfs(node):
        state[node] = GRAY
        #print(node)
        for k in graph.get(node, ()):
            sk = state.get(k, None)
            if sk == GRAY:
                raise ValueError("cycle")
            if sk == BLACK:
                continue
            enter.discard(k)
            dfs(k)
        order.append(node)
        state[node] = BLACK
        
    while enter: dfs(enter.pop())
    return order
126679
def sort_arbitrarily_ordered_nexson(blob):
    
    # otu, node and edge elements have no necessary orger in v0.0 or v1.0
    v = detect_nexson_version(blob)
    nex = get_nexml_el(blob)
    if _is_by_id_hbf(v):
        return blob
    sort_meta_elements(blob)
    for ob in _get_index_list_of_values(nex, 'otus'):
        _inplace_sort_by_id(ob.get('otu', []))
    for tb in _get_index_list_of_values(nex, 'trees'):
        for tree in _get_index_list_of_values(tb, 'tree'):
            _inplace_sort_by_id(tree.get('node', []))
            _inplace_sort_by_id(tree.get('edge', []))
    return blob
953917
public void computeOptimalStrategy() {
		long heavyMin, revHeavyMin, leftMin, revLeftMin, rightMin, revRightMin;
		long min = -1;
		int strategy = -1;
		int parent1 = -1;
		int parent2 = -1;
		boolean[] nodeTypeLeft1 = it1.nodeType[LEFT];
		boolean[] nodeTypeLeft2 = it2.nodeType[LEFT];
		boolean[] nodeTypeRigt1 = it1.nodeType[RIGHT];
		boolean[] nodeTypeRight2 = it2.nodeType[RIGHT];
		boolean[] nodeTypeHeavy1 = it1.nodeType[HEAVY];
		boolean[] nodeTypeHeavy2 = it2.nodeType[HEAVY];
		int[] post2size1 = it1.info[POST2_SIZE];
		int[] post2size2 = it2.info[POST2_SIZE];
		int[] post2descSum1 = it1.info[POST2_DESC_SUM];
		int[] post2descSum2 = it2.info[POST2_DESC_SUM];
		int[] post2krSum1 = it1.info[POST2_KR_SUM];
		int[] post2krSum2 = it2.info[POST2_KR_SUM];
		int[] post2revkrSum1 = it1.info[POST2_REV_KR_SUM];
		int[] post2revkrSum2 = it2.info[POST2_REV_KR_SUM];
		int[] post2parent1 = it1.info[POST2_PARENT];
		int[] post2parent2 = it2.info[POST2_PARENT];

		str = new int[size1][size2];

		// v represents nodes of left input tree in postorder
		// w represents nodes of right input tree in postorder
		for (int v = 0; v < size1; v++) {
			Arrays.fill(costW[0], 0);
			Arrays.fill(costW[1], 0);
			Arrays.fill(costW[2], 0);
			for (int w = 0; w < size2; w++) {
				if (post2size2[w] == 1) {
					// putTree zeros into arrays
					costW[LEFT][w] = 0;
					costW[RIGHT][w] = 0;
					costW[HEAVY][w] = 0;
				}
				if (post2size1[v] == 1) {
					// putTree zeros into arrays
					costV[LEFT][v][w] = 0;
					costV[RIGHT][v][w] = 0;
					costV[HEAVY][v][w] = 0;
				}

				// TODO: some things below may be putTree to outer loop

				// count the minimum + get the strategy
				heavyMin = (long) post2size1[v] * (long) post2descSum2[w]
						+ costV[HEAVY][v][w];
				revHeavyMin = (long) post2size2[w] * (long) post2descSum1[v]
						+ costW[HEAVY][w];

				leftMin = (long) post2size1[v] * (long) post2krSum2[w]
						+ costV[LEFT][v][w];
				revLeftMin = (long) post2size2[w] * (long) post2krSum1[v]
						+ costW[LEFT][w];

				rightMin = (long) post2size1[v] * (long) post2revkrSum2[w]
						+ costV[RIGHT][v][w];
				revRightMin = (long) post2size2[w] * (long) post2revkrSum1[v]
						+ costW[RIGHT][w];

				long[] mins = { leftMin, rightMin, heavyMin, Long.MAX_VALUE,
						revLeftMin, revRightMin, revHeavyMin };

				min = leftMin;
				strategy = 0;
				for (int i = 1; i <= 6; i++) {
					if (mins[i] < min) {
						min = mins[i];
						strategy = i;
					}
				}

				// store the strategy for the minimal cost
				str[v][w] = strategy;

				// fill the cost arrays
				parent1 = post2parent1[v];
				if (parent1 != -1) {
					costV[HEAVY][parent1][w] += nodeTypeHeavy1[v] ? costV[HEAVY][v][w]
							: min;
					costV[RIGHT][parent1][w] += nodeTypeRigt1[v] ? costV[RIGHT][v][w]
							: min;
					costV[LEFT][parent1][w] += nodeTypeLeft1[v] ? costV[LEFT][v][w]
							: min;
				}
				parent2 = post2parent2[w];
				if (parent2 != -1) {
					costW[HEAVY][parent2] += nodeTypeHeavy2[w] ? costW[HEAVY][w]
							: min;
					costW[LEFT][parent2] += nodeTypeLeft2[w] ? costW[LEFT][w]
							: min;
					costW[RIGHT][parent2] += nodeTypeRight2[w] ? costW[RIGHT][w]
							: min;
				}
			}
		}
	}
10095
int bucket(double x) {
        if (x <= min) {
            return 0;
        } else if (x >= max) {
            return counts.length - 1;
        } else {
            return bucketIndex(x);
        }
    }
138010
private static void quickSort(int[] data, final int start, final int end, IntComparator comp) {
    final int len = end - start;
    final int last = end - 1;
    if(len < INSERTION_THRESHOLD) {
      insertionSort(data, start, end, comp);
      return;
    }

    // Choose pivots by looking at five candidates.
    final int seventh = (len >> 3) + (len >> 6) + 1;
    final int m3 = (start + end) >> 1; // middle
    final int m2 = m3 - seventh;
    final int m1 = m2 - seventh;
    final int m4 = m3 + seventh;
    final int m5 = m4 + seventh;

    // Explicit (and optimal) sorting network for 5 elements
    // See Knuth for details.
    sort5(data, m1, m2, m3, m4, m5, comp);

    // Choose the 2 and 4th as pivots, as we want to get three parts
    // Copy to variables v1 and v3, replace them with the start and end
    // Note: do not modify v1 or v3 until we put them back!
    final int lpivot = data[m2];
    final int rpivot = data[m4];
    data[m2] = data[start];
    data[m4] = data[last];

    // A tie is when the two chosen pivots are the same
    final boolean tied = comp.compare(lpivot, rpivot) == 0;

    // Insertion points for pivot areas.
    int left = start + 1;
    int right = last - 1;

    // Note: we merged the ties and no ties cases.
    // This likely is marginally slower, but not at a macro level
    // And you never know with hotspot.
    for(int k = left; k <= right; k++) {
      final int tmp = data[k];
      final int c = comp.compare(tmp, lpivot);
      if(c == 0) {
        continue;
      }
      else if(c < 0) {
        // Traditional quicksort
        data[k] = data[left];
        data[left] = tmp;
        left++;
      }
      else if(tied || comp.compare(tmp, rpivot) > 0) {
        // Now look at the right. First skip correct entries there, too
        while(true) {
          final int tmp2 = data[right];
          if(comp.compare(tmp2, rpivot) > 0 && k < right) {
            right--;
          }
          else {
            break;
          }
        }
        // Now move tmp from k to the right.
        data[k] = data[right];
        data[right] = tmp;
        right--;
        // Test the element we just inserted: left or center?
        if(comp.compare(data[k], lpivot) < 0) {
          final int tmp2 = data[k];
          data[k] = data[left];
          data[left] = tmp2;
          left++;
        } // else: center. cannot be on right.
      }
    }
    // Put the pivot elements back in.
    // Remember: we must not modify v1 and v3 above.
    data[start] = data[left - 1];
    data[left - 1] = lpivot;
    data[last] = data[right + 1];
    data[right + 1] = rpivot;
    // v1 and v3 are now safe to modify again. Perform recursion:
    quickSort(data, start, left - 1, comp);
    // Handle the middle part - if necessary:
    if(!tied) {
      // TODO: the original publication had a special tie handling here.
      // It shouldn't affect correctness, but probably improves situations
      // with a lot of tied elements.
      quickSort(data, left, right + 1, comp);
    }
    quickSort(data, right + 2, end, comp);
  }
1103840
private static void induceSA(BaseArray T, int[] SA, BaseArray C, BaseArray B, int n, int k) {
        int b, i, j;
        int c0, c1;
    /* compute SAl */
        if (C == B) {
            getCounts(T, C, n, k);
        }
        getBuckets(C, B, k, false); /* find starts of buckets */
        j = n - 1;
        b = B.get(c1 = T.get(j));
        SA[b++] = ((0 < j) && (T.get(j - 1) < c1)) ? ~j : j;
        for (i = 0; i < n; ++i) {
            j = SA[i];
            SA[i] = ~j;
            if (0 < j) {
                if ((c0 = T.get(--j)) != c1) {
                    B.set(c1, b);
                    b = B.get(c1 = c0);
                }
                SA[b++] = ((0 < j) && (T.get(j - 1) < c1)) ? ~j : j;
            }
        }
    /* compute SAs */
        if (C == B) {
            getCounts(T, C, n, k);
        }
        getBuckets(C, B, k, true); /* find ends of buckets */
        for (i = n - 1, b = B.get(c1 = 0); 0 <= i; --i) {
            if (0 < (j = SA[i])) {
                if ((c0 = T.get(--j)) != c1) {
                    B.set(c1, b);
                    b = B.get(c1 = c0);
                }
                SA[--b] = ((j == 0) || (T.get(j - 1) > c1)) ? ~j : j;
            } else {
                SA[i] = ~j;
            }
        }
    }
861461
private static void quickSort1(int off, int len, IntComparator comp, Swapper swapper) {
	// Insertion sort on smallest arrays
	if (len < SMALL) {
		for (int i=off; i<len+off; i++)
		for (int j=i; j>off && (comp.compare(j-1,j)>0); j--) {
		    swapper.swap(j, j-1);
		}
		return;
	}

	// Choose a partition element, v
	int m = off + len/2;       // Small arrays, middle element
	if (len > SMALL) {
		int l = off;
		int n = off + len - 1;
		if (len > MEDIUM) {        // Big arrays, pseudomedian of 9
			int s = len/8;
			l = med3(l,     l+s, l+2*s, comp);
			m = med3(m-s,   m,   m+s, comp);
			n = med3(n-2*s, n-s, n, comp);
		}
		m = med3(l, m, n, comp); // Mid-size, med of 3
	}
	//long v = x[m];
	
	// Establish Invariant: v* (<v)* (>v)* v*
	int a = off, b = a, c = off + len - 1, d = c;
	while(true) {
		int comparison;
		while (b <= c && ((comparison=comp.compare(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 !!!
			    swapper.swap(a++, b);
			}
			b++;
		}
		while (c >= b && ((comparison=comp.compare(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 !!!
			    swapper.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 !!!
		swapper.swap(b++, c--);
	}

	// Swap partition elements back to middle
	int s, n = off + len;
	s = java.lang.Math.min(a-off, b-a  );  vecswap(swapper, off, b-s, s);
	s = java.lang.Math.min(d-c,   n-d-1);  vecswap(swapper, b,   n-s, s);

	// Recursively sort non-partition-elements
	if ((s = b-a) > 1) 
		quickSort1(off, s, comp, swapper);
	if ((s = d-c) > 1) 
		quickSort1(n-s, s, comp, swapper);
}
1259210
private static int getBucketCount(SimpleOrderedMap<Object> solrFacets, int defaultCount) {
        List<SimpleOrderedMap<Object>> solrBuckets = (List<SimpleOrderedMap<Object>>) solrFacets.get("buckets");
        if (solrBuckets == null) {
            for (int i = 0; i < solrFacets.size(); i++) {
                if (solrFacets.getName(i).equals("count")) {
                    return (int) solrFacets.getVal(i);
                }
            }
        }
        return defaultCount;
    }
1087864
public void sort(final IndexedSortable s, int p, int r) {
		int recordsPerSegment = s.recordsPerSegment();
		int recordSize = s.recordSize();
		int maxOffset = recordSize * (recordsPerSegment - 1);

		int pN = p / recordsPerSegment;
		int pO = (p % recordsPerSegment) * recordSize;

		int rN = r / recordsPerSegment;
		int rO = (r % recordsPerSegment) * recordSize;

		sortInternal(s, recordsPerSegment, recordSize, maxOffset, p, pN, pO, r, rN, rO, getMaxDepth(r - p));
	}
1072788
private static void quickSort(double[] keys, int[] vals, final int start, final int end) {
    final int len = end - start;
    if(len < INSERTION_THRESHOLD) {
      insertionSort(keys, vals, start, end);
      return;
    }
    final int last = end - 1;

    // Choose pivots by looking at five candidates.
    final int seventh = (len >> 3) + (len >> 6) + 1;
    final int m3 = (start + end) >> 1; // middle
    final int m2 = m3 - seventh;
    final int m1 = m2 - seventh;
    final int m4 = m3 + seventh;
    final int m5 = m4 + seventh;

    // Mixture of insertion and merge sort:
    sort5(keys, vals, m1, m2, m3, m4, m5);

    // Move pivot to the front.
    double pivotkey = keys[m3];
    int pivotval = vals[m3];
    keys[m3] = keys[start];
    vals[m3] = vals[start];

    // The interval to pivotize
    int left = start + 1; // Without pivot
    int right = last; // inclusive

    // This is the classic QuickSort loop:
    while(true) {
      // Move duplicates to right partition, i.e. < here, <= below.
      while(left <= right && keys[left] < pivotkey) {
        left++;
      }
      while(left <= right && pivotkey <= keys[right]) {
        right--;
      }
      if(right <= left) {
        break;
      }
      swap(keys, vals, left, right);
      left++;
      right--;
    }
    // right now points to the last element smaller than the pivot.
    // Move pivot back into the appropriate place
    keys[start] = keys[right];
    vals[start] = vals[right];
    keys[right] = pivotkey;
    vals[right] = pivotval;

    // Recursion when more than one element only:
    if(start + 1 < right) {
      quickSort(keys, vals, start, right);
    }
    int rstart = right + 1;
    // Avoid recursing on duplicates of the pivot:
    while(rstart < last && keys[rstart] <= keys[right]) {
      rstart++;
    }
    // Recurse when _more_ than 1 element only
    if(rstart < last) {
      quickSort(keys, vals, rstart, end);
    }
  }
154143
static <T> void bucketSort(final List<? extends T> c, final int fromIndex, final int toIndex, final Comparator<? super T> cmp) {
        N.checkFromToIndex(fromIndex, toIndex, c == null ? 0 : c.size());

        if ((N.isNullOrEmpty(c) && fromIndex == 0 && toIndex == 0) || fromIndex == toIndex) {
            return;
        }

        if (toIndex - fromIndex < 32) {
            sort(c, fromIndex, toIndex, cmp);
            return;
        }

        final Comparator<? super T> comparator = cmp == null ? Comparators.NATURAL_ORDER : cmp;
        final Multiset<T> multiset = new Multiset<>();
        ListIterator<T> itr = (ListIterator<T>) c.listIterator(fromIndex);
        int i = fromIndex;

        while (itr.hasNext()) {
            if (i++ >= toIndex) {
                break;
            }

            multiset.add(itr.next());
        }

        final Map<T, Integer> m = multiset.toMapSortedBy(new Comparator<Map.Entry<T, MutableInt>>() {
            @Override
            public int compare(Entry<T, MutableInt> a, Entry<T, MutableInt> b) {
                return comparator.compare(a.getKey(), a.getKey());
            }
        });

        itr = (ListIterator<T>) c.listIterator(fromIndex);

        for (Map.Entry<T, Integer> entry : m.entrySet()) {
            final T key = entry.getKey();
            for (int j = 0; j < entry.getValue(); j++) {
                itr.next();
                itr.set(key);
            }
        }
    }