// LazySort also does a sort, but returns an InstanceView and doesn't actually
// reorder the rows, just makes it look like they've been reordered
// See also: Sort
491645
func LazySort(inst FixedDataGrid, direction SortDirection, attrs []AttributeSpec) (FixedDataGrid, error) {
	// Run the sort operation
	sortInstructions := createSortSpec(inst, attrs)

	// Build the row -> row mapping
	_, rows := inst.Size()      // Get the total row count
	rowArr := make([]int, rows) // Create an array of positions
	for i := 0; i < len(rowArr); i++ {
		rowArr[i] = i
	}
	for i := range sortInstructions {
		r1 := rowArr[sortInstructions[i].r1]
		r2 := rowArr[sortInstructions[i].r2]
		// Swap
		rowArr[sortInstructions[i].r1] = r2
		rowArr[sortInstructions[i].r2] = r1
	}
	if direction == Descending {
		for i, j := 0, rows-1; i < j; i, j = i+1, j-1 {
			tmp := rowArr[i]
			rowArr[i] = rowArr[j]
			rowArr[j] = tmp
		}
	}
	// Create a mapping dictionary
	rowMap := make(map[int]int)
	for i, a := range rowArr {
		if i == a {
			continue
		}
		rowMap[i] = a
	}
	// Create the return structure
	ret := NewInstancesViewFromRows(inst, rowMap)
	return ret, nil
}
1359104
func (m *SpiderMenu) Sort(col int, order walk.SortOrder) error {
	m.sortColumn, m.sortOrder = col, order

	sort.Sort(m)

	return m.SorterBase.Sort(col, order)
}
68739
func (m *MockQuery) Sort(arg0 ...string) mongo.Query {
	varargs := []interface{}{}
	for _, a := range arg0 {
		varargs = append(varargs, a)
	}
	ret := m.ctrl.Call(m, "Sort", varargs...)
	ret0, _ := ret[0].(mongo.Query)
	return ret0
}
211943
func safeSort(in []string) []string {
	if sort.StringsAreSorted(in) {
		return in
	}
	out := make([]string, len(in))
	copy(out, in)
	sort.Strings(out)
	return out
}
352752
func Sort(value string, order SortOrder) RequestOptions {
	if order == SortDesc {
		value = value + "+DESC"
	}
	return Filter("Sort", value)
}
39275
func CountingSort(me []int, minVal, maxVal int) (sorted []int) {
	sorted = make([]int, len(me))
	counts := make([]int, maxVal+1-minVal)
	for i := range me {
		counts[me[i]-minVal]++
	}
	for i := 1; i < len(counts); i++ {
		counts[i] += counts[i-1]
	}
	for i := range me {
		sorted[counts[me[i]-minVal]-1] = me[i]
		counts[me[i]-minVal]--
	}
	return
}
975169
func (q *QueryString) SortOrder(name string) (os []*SortOrder, err error) {
	defer func() {
		if rec := recover(); rec != nil {
			err = rec.(error)
		}
	}()

	raw, ok := q.fields[name]
	if !ok {
		return nil, fmt.Errorf("field not found: %q", name)
	}

	os, raw = parseSortOrders(raw)
	if len(raw) != 0 {
		os = nil
		err = UnexpectedEndOfSortOrders
	}

	return
}
169330
func (v Versions) Sort() {
	sort.Slice(v, func(i, j int) bool {
		return v[i].NewerThan(v[j])
	})
}
719353
func Sort(key string, list interface{}) (out []interface{}, err error) {
	if list == nil {
		return nil, nil
	}

	ia, err := interfaceSlice(list)
	if err != nil {
		return nil, err
	}
	// if the types are all the same, we can sort the slice
	if sameTypes(ia) {
		s := make([]interface{}, len(ia))
		// make a copy so the original is unmodified
		copy(s, ia)
		sort.SliceStable(s, func(i, j int) bool {
			return lessThan(key)(s[i], s[j])
		})
		return s, nil
	}
	return ia, nil
}
627887
func (rb *route) PushOrderByRand() {
	rb.Select.(*sqlparser.Select).OrderBy = sqlparser.OrderBy{&sqlparser.Order{Expr: &sqlparser.FuncExpr{Name: sqlparser.NewColIdent("rand")}}}
}
1350895
func (r *ReindexSource) Sort(field string, ascending bool) *ReindexSource {
	r.request = r.request.Sort(field, ascending)
	return r
}
888141
func (pb *primitiveBuilder) pushOrderBy(orderBy sqlparser.OrderBy) error {
	if oa, ok := pb.bldr.(*orderedAggregate); ok {
		return oa.PushOrderBy(pb, orderBy)
	}

	switch len(orderBy) {
	case 0:
		return nil
	case 1:
		// Special handling for ORDER BY NULL. Push it everywhere.
		if _, ok := orderBy[0].Expr.(*sqlparser.NullVal); ok {
			pb.bldr.PushOrderByNull()
			return nil
		} else if f, ok := orderBy[0].Expr.(*sqlparser.FuncExpr); ok {
			if f.Name.Lowered() == "rand" {
				pb.bldr.PushOrderByRand()
				return nil
			}
		}
	}

	firstRB, ok := pb.bldr.First().(*route)
	if !ok {
		return errors.New("unsupported: cannot order by on a cross-shard subquery")
	}
	for _, order := range orderBy {
		if node, ok := order.Expr.(*sqlparser.SQLVal); ok {
			// This block handles constructs that use ordinals for 'ORDER BY'. For example:
			// SELECT a, b, c FROM t1, t2 ORDER BY 1, 2, 3.
			num, err := ResultFromNumber(pb.st.ResultColumns, node)
			if err != nil {
				return err
			}
			target := pb.st.ResultColumns[num].column.Origin()
			if target != firstRB {
				return errors.New("unsupported: order by spans across shards")
			}
		} else {
			// Analyze column references within the expression to make sure they all
			// go to the same route.
			err := sqlparser.Walk(func(node sqlparser.SQLNode) (kontinue bool, err error) {
				switch node := node.(type) {
				case *sqlparser.ColName:
					target, _, err := pb.st.Find(node)
					if err != nil {
						return false, err
					}
					if target != firstRB {
						return false, errors.New("unsupported: order by spans across shards")
					}
				case *sqlparser.Subquery:
					return false, errors.New("unsupported: order by has subquery")
				}
				return true, nil
			}, order.Expr)
			if err != nil {
				return err
			}
		}

		// There were no errors. We can push the order by to the left-most route.
		if err := firstRB.PushOrderBy(order); err != nil {
			return err
		}
	}
	return nil
}
228019
func (db *DB) XLSort(key []byte, offset int, size int, alpha bool, desc bool, sortBy []byte, sortGet [][]byte) ([][]byte, error) {
	values, err := db.LRange(key, 0, -1)

	if err != nil {
		return nil, err
	}

	return db.xsort(values, offset, size, alpha, desc, sortBy, sortGet)
}
444609
func (b *batch) RequestSort() bool {
	if b == deletedChildBatchMarker {
		return true
	}

	// false because we must never wait for sorter else it can deadlock.
	sorted := b.segment.RequestSort(false)

	for _, childBatch := range b.childBatches {
		sorted = childBatch.RequestSort() && sorted
	}

	return sorted
}
1283420
func (v VarBinds) Sort() VarBinds {
	c := make(VarBinds, len(v))
	copy(c, v)
	sort.Sort(sortableVarBinds{c})
	return c
}
205881
func (c *Callback) reorder() {
	var creates, updates, deletes, queries, rowQueries []*CallbackProcessor

	for _, processor := range c.processors {
		if processor.name != "" {
			switch processor.kind {
			case "create":
				creates = append(creates, processor)
			case "update":
				updates = append(updates, processor)
			case "delete":
				deletes = append(deletes, processor)
			case "query":
				queries = append(queries, processor)
			case "row_query":
				rowQueries = append(rowQueries, processor)
			}
		}
	}

	c.creates = sortProcessors(creates)
	c.updates = sortProcessors(updates)
	c.deletes = sortProcessors(deletes)
	c.queries = sortProcessors(queries)
	c.rowQueries = sortProcessors(rowQueries)
}
770256
func heapSort_func(data lessSwap, a, b int) {
	first := a
	lo := 0
	hi := b - a
	for i := (hi - 1) / 2; i >= 0; i-- {
		siftDown_func(data, i, hi, first)
	}
	for i := hi - 1; i >= 0; i-- {
		data.Swap(first, first+i)
		siftDown_func(data, lo, i, first)
	}
}