// Quicksort, following Bentley and McIlroy,
// ``Engineering a Sort Function,'' SP&E November 1993.
// medianOfThree moves the median of the three values data[a], data[b], data[c] into data[a].
334249
func medianOfThree(data []int, a, b, c int) {
	m0 := b
	m1 := a
	m2 := c
	// bubble sort on 3 elements
	if data[m1] < data[m0] {
		data[m1], data[m0] = data[m0], data[m1]
	}
	if data[m2] < data[m1] {
		data[m2], data[m1] = data[m1], data[m2]
	}
	if data[m1] < data[m0] {
		data[m1], data[m0] = data[m0], data[m1]
	}
	// now data[m0] <= data[m1] <= data[m2]
}
545086
func (e EdgeMap) Sort() []*Edge {
	el := make(edgeList, 0, len(e))
	for _, w := range e {
		el = append(el, w)
	}

	sort.Sort(el)
	return el
}
1211754
func (ms *multiIfAddrSorter) Sort(ifAddrs IfAddrs) {
	ms.ifAddrs = ifAddrs
	sort.Sort(ms)
}
37927
func median(data sort.Interface, lo, hi int) int {
	m := (lo + hi) / 2
	d := (hi - lo) / 8
	// Move median into the middle.
	mot := func(ml, mm, mh int) {
		if data.Less(mm, ml) {
			data.Swap(mm, ml)
		}
		if data.Less(mh, mm) {
			data.Swap(mh, mm)
		}
		if data.Less(mm, ml) {
			data.Swap(mm, ml)
		}
	}
	// Get low, middle, and high median.
	if hi-lo > 40 {
		mot(lo+d, lo, lo+2*d)
		mot(m-d, m, m+d)
		mot(hi-d, hi, hi-2*d)
	}
	// Get combined median.
	mot(lo, m, hi)
	return m
}
957453
func (t *TDigest) Quantile(q float64) float64 {
	if q < 0 || q > 1 {
		panic("q must be between 0 and 1 (inclusive)")
	}

	if t.summary.Len() == 0 {
		return math.NaN()
	} else if t.summary.Len() == 1 {
		return t.summary.Mean(0)
	}

	index := q * float64(t.count-1)
	previousMean := math.NaN()
	previousIndex := float64(0)
	next, total := t.summary.FloorSum(index)

	if next > 0 {
		previousMean = t.summary.Mean(next - 1)
		previousIndex = total - float64(t.summary.Count(next-1)+1)/2
	}

	for {
		nextIndex := total + float64(t.summary.Count(next)-1)/2
		if nextIndex >= index {
			if math.IsNaN(previousMean) {
				// the index is before the 1st centroid
				if nextIndex == previousIndex {
					return t.summary.Mean(next)
				}
				// assume linear growth
				nextIndex2 := total + float64(t.summary.Count(next)) + float64(t.summary.Count(next+1)-1)/2
				previousMean = (nextIndex2*t.summary.Mean(next) - nextIndex*t.summary.Mean(next+1)) / (nextIndex2 - nextIndex)
			}
			// common case: two centroids found, the result in in between
			return _quantile(index, previousIndex, nextIndex, previousMean, t.summary.Mean(next))
		} else if next+1 == t.summary.Len() {
			// the index is after the last centroid
			nextIndex2 := float64(t.count - 1)
			nextMean2 := (t.summary.Mean(next)*(nextIndex2-previousIndex) - previousMean*(nextIndex2-nextIndex)) / (nextIndex - previousIndex)
			return _quantile(index, nextIndex, nextIndex2, t.summary.Mean(next), nextMean2)
		}
		total += float64(t.summary.Count(next))
		previousMean = t.summary.Mean(next)
		previousIndex = nextIndex
		next++
	}
	// unreachable
}
266725
func ParsePriority(buff []byte, cursor *int, l int) (Priority, error) {
	pri := newPriority(0)

	if l <= 0 {
		return pri, ErrPriorityEmpty
	}

	if buff[*cursor] != PRI_PART_START {
		return pri, ErrPriorityNoStart
	}

	i := 1
	priDigit := 0

	for i < l {
		if i >= 5 {
			return pri, ErrPriorityTooLong
		}

		c := buff[i]

		if c == PRI_PART_END {
			if i == 1 {
				return pri, ErrPriorityTooShort
			}

			*cursor = i + 1
			return newPriority(priDigit), nil
		}

		if IsDigit(c) {
			v, e := strconv.Atoi(string(c))
			if e != nil {
				return pri, e
			}

			priDigit = (priDigit * 10) + v
		} else {
			return pri, ErrPriorityNonDigit
		}

		i++
	}

	return pri, ErrPriorityNoEnd
}
519579
func Sort(data sort.Interface) {
	done := make(chan bool)

	go parallelQuickSort(data, 0, data.Len()-1, done)

	<-done
}
28398
func (b *Sortable) Comparator(k string, less StringComparator) SortComparator {
	return func(i, j int) bool {
		return less(b.Data[i].Get(k), b.Data[j].Get(k))
	}
}
1035567
func sortParameters(params map[string]string, format string) []string {
	// sort by key
	keys := make([]string, len(params))
	i := 0
	for key := range params {
		keys[i] = key
		i++
	}
	sort.Strings(keys)
	// parameter join
	pairs := make([]string, len(params))
	for i, key := range keys {
		pairs[i] = fmt.Sprintf(format, key, params[key])
	}
	return pairs
}
566422
func NewSortedSlice(opts ...int) (ss SortedSlice) {
	l, c := 0, 0
	if len(opts) >= 1 {
		l = opts[0]
	}
	if len(opts) >= 2 {
		c = opts[1]
	}
	ss.s = make([]Sortable, l, c)
	return
}
999365
func (self *Query) Sort(fields ...string) *Query {

	self.sort = append(self.sort, fields...)

	return self
}
1367702
func (b *Sortable) AsSortProcess() *SortProcess {
	return &SortProcess{
		Keys: b.Keys,
		AsSort: func(data []Record) sort.Interface {
			b.Data = data
			return b
		},
	}
}
1004730
func (sf64 *SliceFloat64) Median() (float64, error) {
	if len(sf64.Elements) == 0 {
		return 0, errors.New("List is empty")
	}
	if !sort.Float64sAreSorted(sf64.Elements) {
		sort.Float64s(sf64.Elements)
	}
	mid := int64(float64(len(sf64.Elements)) / 2)
	return sf64.Elements[mid], nil
}
1122303
func average(name string, fun func(), benchSize int) {
	numThreads := runtime.GOMAXPROCS(-1)
	wp := new(sync.WaitGroup)
	iter := float64(benchSize)
	start := float64(time.Now().UTC().UnixNano())
	// Run function across multiple goroutines
	for i := 0; i < benchSize; i += benchSize / numThreads {
		wp.Add(1)
		go func() {
			defer wp.Done()
			for j := 0; j < benchSize/numThreads; j++ {
				fun()
			}
		}()
	}
	wp.Wait()
	end := float64(time.Now().UTC().UnixNano())
	fmt.Printf("%s %d: %d ns/iter, %d iter/sec\n", name, int(benchSize), int((end-start)/iter), int(1000000000/((end-start)/iter)))
}
244733
func sequentialQuickSort(data sort.Interface, lo, hi int) {
	if hi-lo > sequentialThreshold {
		// Use sequential quicksort.
		plo, phi := partition(data, lo, hi)
		sequentialQuickSort(data, lo, plo)
		sequentialQuickSort(data, phi, hi)
	} else {
		// Use insertion sort.
		insertionSort(data, lo, hi)
	}
}
399635
func (h *BytesRefHash) Sort(comp func(a, b []byte) bool) []int {
	compact := h.compact()
	s := newBytesRefIntroSorter(h, compact, comp)
	s.Sort(0, h.count)
	// TODO remove this
	// for i, _ := range compact {
	// 	if compact[i+1] == -1 {
	// 		break
	// 	}
	// 	assert(!s.Less(i+1, i))
	// 	if ok := !s.Less(i+1, i); !ok {
	// 		fmt.Println("DEBUG1", compact)
	// 		assert(ok)
	// 	}
	// }
	return compact
}
803101
func (comp *orderedOrdering) Sort(dimensions map[string]string) []string {
	dims := make([]string, 0, len(dimensions))
	for k := range dimensions {
		dims = append(dims, k)
	}
	req := &orderedDimensionSortRequest{
		comparor:     comp,
		dimensions:   dimensions,
		currentOrder: dims,
	}
	sort.Sort(req)
	return req.currentOrder
}