// Code generated by gen_sort_variants.go; DO NOT EDIT.

// Copyright 2022 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package slices

// insertionSortCmpFunc sorts data[a:b] using insertion sort.
func insertionSortCmpFunc[ any]( [], ,  int,  func(,  ) int) {
	for  :=  + 1;  < ; ++ {
		for  := ;  >  && (([], [-1]) < 0); -- {
			[], [-1] = [-1], []
		}
	}
}

// siftDownCmpFunc implements the heap property on data[lo:hi].
// first is an offset into the array where the root of the heap lies.
func siftDownCmpFunc[ any]( [], , ,  int,  func(,  ) int) {
	 := 
	for {
		 := 2* + 1
		if  >=  {
			break
		}
		if +1 <  && (([+], [++1]) < 0) {
			++
		}
		if !(([+], [+]) < 0) {
			return
		}
		[+], [+] = [+], [+]
		 = 
	}
}

func heapSortCmpFunc[ any]( [], ,  int,  func(,  ) int) {
	 := 
	 := 0
	 :=  - 

	// Build heap with greatest element at top.
	for  := ( - 1) / 2;  >= 0; -- {
		siftDownCmpFunc(, , , , )
	}

	// Pop elements, largest first, into end of data.
	for  :=  - 1;  >= 0; -- {
		[], [+] = [+], []
		siftDownCmpFunc(, , , , )
	}
}

// pdqsortCmpFunc sorts data[a:b].
// The algorithm based on pattern-defeating quicksort(pdqsort), but without the optimizations from BlockQuicksort.
// pdqsort paper: https://arxiv.org/pdf/2106.05123.pdf
// C++ implementation: https://github.com/orlp/pdqsort
// Rust implementation: https://docs.rs/pdqsort/latest/pdqsort/
// limit is the number of allowed bad (very unbalanced) pivots before falling back to heapsort.
func pdqsortCmpFunc[ any]( [], , ,  int,  func(,  ) int) {
	const  = 12

	var (
		    = true // whether the last partitioning was reasonably balanced
		 = true // whether the slice was already partitioned
	)

	for {
		 :=  - 

		if  <=  {
			insertionSortCmpFunc(, , , )
			return
		}

		// Fall back to heapsort if too many bad choices were made.
		if  == 0 {
			heapSortCmpFunc(, , , )
			return
		}

		// If the last partitioning was imbalanced, we need to breaking patterns.
		if ! {
			breakPatternsCmpFunc(, , , )
			--
		}

		,  := choosePivotCmpFunc(, , , )
		if  == decreasingHint {
			reverseRangeCmpFunc(, , , )
			// The chosen pivot was pivot-a elements after the start of the array.
			// After reversing it is pivot-a elements before the end of the array.
			// The idea came from Rust's implementation.
			 = ( - 1) - ( - )
			 = increasingHint
		}

		// The slice is likely already sorted.
		if  &&  &&  == increasingHint {
			if partialInsertionSortCmpFunc(, , , ) {
				return
			}
		}

		// Probably the slice contains many duplicate elements, partition the slice into
		// elements equal to and elements greater than the pivot.
		if  > 0 && !(([-1], []) < 0) {
			 := partitionEqualCmpFunc(, , , , )
			 = 
			continue
		}

		,  := partitionCmpFunc(, , , , )
		 = 

		,  := -, -
		 :=  / 8
		if  <  {
			 =  >= 
			(, , , , )
			 =  + 1
		} else {
			 =  >= 
			(, +1, , , )
			 = 
		}
	}
}

// partitionCmpFunc does one quicksort partition.
// Let p = data[pivot]
// Moves elements in data[a:b] around, so that data[i]<p and data[j]>=p for i<newpivot and j>newpivot.
// On return, data[newpivot] = p
func partitionCmpFunc[ any]( [], , ,  int,  func(,  ) int) ( int,  bool) {
	[], [] = [], []
	,  := +1, -1 // i and j are inclusive of the elements remaining to be partitioned

	for  <=  && (([], []) < 0) {
		++
	}
	for  <=  && !(([], []) < 0) {
		--
	}
	if  >  {
		[], [] = [], []
		return , true
	}
	[], [] = [], []
	++
	--

	for {
		for  <=  && (([], []) < 0) {
			++
		}
		for  <=  && !(([], []) < 0) {
			--
		}
		if  >  {
			break
		}
		[], [] = [], []
		++
		--
	}
	[], [] = [], []
	return , false
}

// partitionEqualCmpFunc partitions data[a:b] into elements equal to data[pivot] followed by elements greater than data[pivot].
// It assumed that data[a:b] does not contain elements smaller than the data[pivot].
func partitionEqualCmpFunc[ any]( [], , ,  int,  func(,  ) int) ( int) {
	[], [] = [], []
	,  := +1, -1 // i and j are inclusive of the elements remaining to be partitioned

	for {
		for  <=  && !(([], []) < 0) {
			++
		}
		for  <=  && (([], []) < 0) {
			--
		}
		if  >  {
			break
		}
		[], [] = [], []
		++
		--
	}
	return 
}

// partialInsertionSortCmpFunc partially sorts a slice, returns true if the slice is sorted at the end.
func partialInsertionSortCmpFunc[ any]( [], ,  int,  func(,  ) int) bool {
	const (
		         = 5  // maximum number of adjacent out-of-order pairs that will get shifted
		 = 50 // don't shift any elements on short arrays
	)
	 :=  + 1
	for  := 0;  < ; ++ {
		for  <  && !(([], [-1]) < 0) {
			++
		}

		if  ==  {
			return true
		}

		if - <  {
			return false
		}

		[], [-1] = [-1], []

		// Shift the smaller one to the left.
		if - >= 2 {
			for  :=  - 1;  >= 1; -- {
				if !(([], [-1]) < 0) {
					break
				}
				[], [-1] = [-1], []
			}
		}
		// Shift the greater one to the right.
		if - >= 2 {
			for  :=  + 1;  < ; ++ {
				if !(([], [-1]) < 0) {
					break
				}
				[], [-1] = [-1], []
			}
		}
	}
	return false
}

// breakPatternsCmpFunc scatters some elements around in an attempt to break some patterns
// that might cause imbalanced partitions in quicksort.
func breakPatternsCmpFunc[ any]( [], ,  int,  func(,  ) int) {
	 :=  - 
	if  >= 8 {
		 := xorshift()
		 := nextPowerOfTwo()

		for  :=  + (/4)*2 - 1;  <= +(/4)*2+1; ++ {
			 := int(uint(.Next()) & ( - 1))
			if  >=  {
				 -= 
			}
			[], [+] = [+], []
		}
	}
}

// choosePivotCmpFunc chooses a pivot in data[a:b].
//
// [0,8): chooses a static pivot.
// [8,shortestNinther): uses the simple median-of-three method.
// [shortestNinther,∞): uses the Tukey ninther method.
func choosePivotCmpFunc[ any]( [], ,  int,  func(,  ) int) ( int,  sortedHint) {
	const (
		 = 50
		        = 4 * 3
	)

	 :=  - 

	var (
		 int
		     =  + /4*1
		     =  + /4*2
		     =  + /4*3
	)

	if  >= 8 {
		if  >=  {
			// Tukey ninther method, the idea came from Rust's implementation.
			 = medianAdjacentCmpFunc(, , &, )
			 = medianAdjacentCmpFunc(, , &, )
			 = medianAdjacentCmpFunc(, , &, )
		}
		// Find the median among i, j, k and stores it into j.
		 = medianCmpFunc(, , , , &, )
	}

	switch  {
	case 0:
		return , increasingHint
	case :
		return , decreasingHint
	default:
		return , unknownHint
	}
}

// order2CmpFunc returns x,y where data[x] <= data[y], where x,y=a,b or x,y=b,a.
func order2CmpFunc[ any]( [], ,  int,  *int,  func(,  ) int) (int, int) {
	if ([], []) < 0 {
		*++
		return , 
	}
	return , 
}

// medianCmpFunc returns x where data[x] is the median of data[a],data[b],data[c], where x is a, b, or c.
func medianCmpFunc[ any]( [], , ,  int,  *int,  func(,  ) int) int {
	,  = order2CmpFunc(, , , , )
	,  = order2CmpFunc(, , , , )
	,  = order2CmpFunc(, , , , )
	return 
}

// medianAdjacentCmpFunc finds the median of data[a - 1], data[a], data[a + 1] and stores the index into a.
func medianAdjacentCmpFunc[ any]( [],  int,  *int,  func(,  ) int) int {
	return medianCmpFunc(, -1, , +1, , )
}

func reverseRangeCmpFunc[ any]( [], ,  int,  func(,  ) int) {
	 := 
	 :=  - 1
	for  <  {
		[], [] = [], []
		++
		--
	}
}

func swapRangeCmpFunc[ any]( [], , ,  int,  func(,  ) int) {
	for  := 0;  < ; ++ {
		[+], [+] = [+], [+]
	}
}

func stableCmpFunc[ any]( [],  int,  func(,  ) int) {
	 := 20 // must be > 0
	,  := 0, 
	for  <=  {
		insertionSortCmpFunc(, , , )
		 = 
		 += 
	}
	insertionSortCmpFunc(, , , )

	for  <  {
		,  = 0, 2*
		for  <=  {
			symMergeCmpFunc(, , +, , )
			 = 
			 += 2 * 
		}
		if  :=  + ;  <  {
			symMergeCmpFunc(, , , , )
		}
		 *= 2
	}
}

// symMergeCmpFunc merges the two sorted subsequences data[a:m] and data[m:b] using
// the SymMerge algorithm from Pok-Son Kim and Arne Kutzner, "Stable Minimum
// Storage Merging by Symmetric Comparisons", in Susanne Albers and Tomasz
// Radzik, editors, Algorithms - ESA 2004, volume 3221 of Lecture Notes in
// Computer Science, pages 714-723. Springer, 2004.
//
// Let M = m-a and N = b-n. Wolog M < N.
// The recursion depth is bound by ceil(log(N+M)).
// The algorithm needs O(M*log(N/M + 1)) calls to data.Less.
// The algorithm needs O((M+N)*log(M)) calls to data.Swap.
//
// The paper gives O((M+N)*log(M)) as the number of assignments assuming a
// rotation algorithm which uses O(M+N+gcd(M+N)) assignments. The argumentation
// in the paper carries through for Swap operations, especially as the block
// swapping rotate uses only O(M+N) Swaps.
//
// symMerge assumes non-degenerate arguments: a < m && m < b.
// Having the caller check this condition eliminates many leaf recursion calls,
// which improves performance.
func symMergeCmpFunc[ any]( [], , ,  int,  func(,  ) int) {
	// Avoid unnecessary recursions of symMerge
	// by direct insertion of data[a] into data[m:b]
	// if data[a:m] only contains one element.
	if - == 1 {
		// Use binary search to find the lowest index i
		// such that data[i] >= data[a] for m <= i < b.
		// Exit the search loop with i == b in case no such index exists.
		 := 
		 := 
		for  <  {
			 := int(uint(+) >> 1)
			if ([], []) < 0 {
				 =  + 1
			} else {
				 = 
			}
		}
		// Swap values until data[a] reaches the position before i.
		for  := ;  < -1; ++ {
			[], [+1] = [+1], []
		}
		return
	}

	// Avoid unnecessary recursions of symMerge
	// by direct insertion of data[m] into data[a:m]
	// if data[m:b] only contains one element.
	if - == 1 {
		// Use binary search to find the lowest index i
		// such that data[i] > data[m] for a <= i < m.
		// Exit the search loop with i == m in case no such index exists.
		 := 
		 := 
		for  <  {
			 := int(uint(+) >> 1)
			if !(([], []) < 0) {
				 =  + 1
			} else {
				 = 
			}
		}
		// Swap values until data[m] reaches the position i.
		for  := ;  > ; -- {
			[], [-1] = [-1], []
		}
		return
	}

	 := int(uint(+) >> 1)
	 :=  + 
	var ,  int
	if  >  {
		 =  - 
		 = 
	} else {
		 = 
		 = 
	}
	 :=  - 1

	for  <  {
		 := int(uint(+) >> 1)
		if !(([-], []) < 0) {
			 =  + 1
		} else {
			 = 
		}
	}

	 :=  - 
	if  <  &&  <  {
		rotateCmpFunc(, , , , )
	}
	if  <  &&  <  {
		(, , , , )
	}
	if  <  &&  <  {
		(, , , , )
	}
}

// rotateCmpFunc rotates two consecutive blocks u = data[a:m] and v = data[m:b] in data:
// Data of the form 'x u v y' is changed to 'x v u y'.
// rotate performs at most b-a many calls to data.Swap,
// and it assumes non-degenerate arguments: a < m && m < b.
func rotateCmpFunc[ any]( [], , ,  int,  func(,  ) int) {
	 :=  - 
	 :=  - 

	for  !=  {
		if  >  {
			swapRangeCmpFunc(, -, , , )
			 -= 
		} else {
			swapRangeCmpFunc(, -, +-, , )
			 -= 
		}
	}
	// i == j
	swapRangeCmpFunc(, -, , , )
}