codekingpro/portable-devtools

1// Code generated by gen_sort_variants.go; DO NOT EDIT.2 3// Copyright 2022 The Go Authors. All rights reserved.4// Use of this source code is governed by a BSD-style5// license that can be found in the LICENSE file.6 7package sort8 9// insertionSort sorts data[a:b] using insertion sort.10func insertionSort(data Interface, a, b int) {11	for i := a + 1; i < b; i++ {12		for j := i; j > a && data.Less(j, j-1); j-- {13			data.Swap(j, j-1)14		}15	}16}17 18// siftDown implements the heap property on data[lo:hi].19// first is an offset into the array where the root of the heap lies.20func siftDown(data Interface, lo, hi, first int) {21	root := lo22	for {23		child := 2*root + 124		if child >= hi {25			break26		}27		if child+1 < hi && data.Less(first+child, first+child+1) {28			child++29		}30		if !data.Less(first+root, first+child) {31			return32		}33		data.Swap(first+root, first+child)34		root = child35	}36}37 38func heapSort(data Interface, a, b int) {39	first := a40	lo := 041	hi := b - a42 43	// Build heap with greatest element at top.44	for i := (hi - 1) / 2; i >= 0; i-- {45		siftDown(data, i, hi, first)46	}47 48	// Pop elements, largest first, into end of data.49	for i := hi - 1; i >= 0; i-- {50		data.Swap(first, first+i)51		siftDown(data, lo, i, first)52	}53}54 55// pdqsort sorts data[a:b].56// The algorithm based on pattern-defeating quicksort(pdqsort), but without the optimizations from BlockQuicksort.57// pdqsort paper: https://arxiv.org/pdf/2106.05123.pdf58// C++ implementation: https://github.com/orlp/pdqsort59// Rust implementation: https://docs.rs/pdqsort/latest/pdqsort/60// limit is the number of allowed bad (very unbalanced) pivots before falling back to heapsort.61func pdqsort(data Interface, a, b, limit int) {62	const maxInsertion = 1263 64	var (65		wasBalanced    = true // whether the last partitioning was reasonably balanced66		wasPartitioned = true // whether the slice was already partitioned67	)68 69	for {70		length := b - a71 72		if length <= maxInsertion {73			insertionSort(data, a, b)74			return75		}76 77		// Fall back to heapsort if too many bad choices were made.78		if limit == 0 {79			heapSort(data, a, b)80			return81		}82 83		// If the last partitioning was imbalanced, we need to breaking patterns.84		if !wasBalanced {85			breakPatterns(data, a, b)86			limit--87		}88 89		pivot, hint := choosePivot(data, a, b)90		if hint == decreasingHint {91			reverseRange(data, a, b)92			// The chosen pivot was pivot-a elements after the start of the array.93			// After reversing it is pivot-a elements before the end of the array.94			// The idea came from Rust's implementation.95			pivot = (b - 1) - (pivot - a)96			hint = increasingHint97		}98 99		// The slice is likely already sorted.100		if wasBalanced && wasPartitioned && hint == increasingHint {101			if partialInsertionSort(data, a, b) {102				return103			}104		}105 106		// Probably the slice contains many duplicate elements, partition the slice into107		// elements equal to and elements greater than the pivot.108		if a > 0 && !data.Less(a-1, pivot) {109			mid := partitionEqual(data, a, b, pivot)110			a = mid111			continue112		}113 114		mid, alreadyPartitioned := partition(data, a, b, pivot)115		wasPartitioned = alreadyPartitioned116 117		leftLen, rightLen := mid-a, b-mid118		balanceThreshold := length / 8119		if leftLen < rightLen {120			wasBalanced = leftLen >= balanceThreshold121			pdqsort(data, a, mid, limit)122			a = mid + 1123		} else {124			wasBalanced = rightLen >= balanceThreshold125			pdqsort(data, mid+1, b, limit)126			b = mid127		}128	}129}130 131// partition does one quicksort partition.132// Let p = data[pivot]133// Moves elements in data[a:b] around, so that data[i]<p and data[j]>=p for i<newpivot and j>newpivot.134// On return, data[newpivot] = p135func partition(data Interface, a, b, pivot int) (newpivot int, alreadyPartitioned bool) {136	data.Swap(a, pivot)137	i, j := a+1, b-1 // i and j are inclusive of the elements remaining to be partitioned138 139	for i <= j && data.Less(i, a) {140		i++141	}142	for i <= j && !data.Less(j, a) {143		j--144	}145	if i > j {146		data.Swap(j, a)147		return j, true148	}149	data.Swap(i, j)150	i++151	j--152 153	for {154		for i <= j && data.Less(i, a) {155			i++156		}157		for i <= j && !data.Less(j, a) {158			j--159		}160		if i > j {161			break162		}163		data.Swap(i, j)164		i++165		j--166	}167	data.Swap(j, a)168	return j, false169}170 171// partitionEqual partitions data[a:b] into elements equal to data[pivot] followed by elements greater than data[pivot].172// It assumed that data[a:b] does not contain elements smaller than the data[pivot].173func partitionEqual(data Interface, a, b, pivot int) (newpivot int) {174	data.Swap(a, pivot)175	i, j := a+1, b-1 // i and j are inclusive of the elements remaining to be partitioned176 177	for {178		for i <= j && !data.Less(a, i) {179			i++180		}181		for i <= j && data.Less(a, j) {182			j--183		}184		if i > j {185			break186		}187		data.Swap(i, j)188		i++189		j--190	}191	return i192}193 194// partialInsertionSort partially sorts a slice, returns true if the slice is sorted at the end.195func partialInsertionSort(data Interface, a, b int) bool {196	const (197		maxSteps         = 5  // maximum number of adjacent out-of-order pairs that will get shifted198		shortestShifting = 50 // don't shift any elements on short arrays199	)200	i := a + 1201	for j := 0; j < maxSteps; j++ {202		for i < b && !data.Less(i, i-1) {203			i++204		}205 206		if i == b {207			return true208		}209 210		if b-a < shortestShifting {211			return false212		}213 214		data.Swap(i, i-1)215 216		// Shift the smaller one to the left.217		if i-a >= 2 {218			for j := i - 1; j >= 1; j-- {219				if !data.Less(j, j-1) {220					break221				}222				data.Swap(j, j-1)223			}224		}225		// Shift the greater one to the right.226		if b-i >= 2 {227			for j := i + 1; j < b; j++ {228				if !data.Less(j, j-1) {229					break230				}231				data.Swap(j, j-1)232			}233		}234	}235	return false236}237 238// breakPatterns scatters some elements around in an attempt to break some patterns239// that might cause imbalanced partitions in quicksort.240func breakPatterns(data Interface, a, b int) {241	length := b - a242	if length >= 8 {243		random := xorshift(length)244		modulus := nextPowerOfTwo(length)245 246		for idx := a + (length/4)*2 - 1; idx <= a+(length/4)*2+1; idx++ {247			other := int(uint(random.Next()) & (modulus - 1))248			if other >= length {249				other -= length250			}251			data.Swap(idx, a+other)252		}253	}254}255 256// choosePivot chooses a pivot in data[a:b].257//258// [0,8): chooses a static pivot.259// [8,shortestNinther): uses the simple median-of-three method.260// [shortestNinther,∞): uses the Tukey ninther method.261func choosePivot(data Interface, a, b int) (pivot int, hint sortedHint) {262	const (263		shortestNinther = 50264		maxSwaps        = 4 * 3265	)266 267	l := b - a268 269	var (270		swaps int271		i     = a + l/4*1272		j     = a + l/4*2273		k     = a + l/4*3274	)275 276	if l >= 8 {277		if l >= shortestNinther {278			// Tukey ninther method, the idea came from Rust's implementation.279			i = medianAdjacent(data, i, &swaps)280			j = medianAdjacent(data, j, &swaps)281			k = medianAdjacent(data, k, &swaps)282		}283		// Find the median among i, j, k and stores it into j.284		j = median(data, i, j, k, &swaps)285	}286 287	switch swaps {288	case 0:289		return j, increasingHint290	case maxSwaps:291		return j, decreasingHint292	default:293		return j, unknownHint294	}295}296 297// order2 returns x,y where data[x] <= data[y], where x,y=a,b or x,y=b,a.298func order2(data Interface, a, b int, swaps *int) (int, int) {299	if data.Less(b, a) {300		*swaps++301		return b, a302	}303	return a, b304}305 306// median returns x where data[x] is the median of data[a],data[b],data[c], where x is a, b, or c.307func median(data Interface, a, b, c int, swaps *int) int {308	a, b = order2(data, a, b, swaps)309	b, c = order2(data, b, c, swaps)310	a, b = order2(data, a, b, swaps)311	return b312}313 314// medianAdjacent finds the median of data[a - 1], data[a], data[a + 1] and stores the index into a.315func medianAdjacent(data Interface, a int, swaps *int) int {316	return median(data, a-1, a, a+1, swaps)317}318 319func reverseRange(data Interface, a, b int) {320	i := a321	j := b - 1322	for i < j {323		data.Swap(i, j)324		i++325		j--326	}327}328 329func swapRange(data Interface, a, b, n int) {330	for i := 0; i < n; i++ {331		data.Swap(a+i, b+i)332	}333}334 335func stable(data Interface, n int) {336	blockSize := 20 // must be > 0337	a, b := 0, blockSize338	for b <= n {339		insertionSort(data, a, b)340		a = b341		b += blockSize342	}343	insertionSort(data, a, n)344 345	for blockSize < n {346		a, b = 0, 2*blockSize347		for b <= n {348			symMerge(data, a, a+blockSize, b)349			a = b350			b += 2 * blockSize351		}352		if m := a + blockSize; m < n {353			symMerge(data, a, m, n)354		}355		blockSize *= 2356	}357}358 359// symMerge merges the two sorted subsequences data[a:m] and data[m:b] using360// the SymMerge algorithm from Pok-Son Kim and Arne Kutzner, "Stable Minimum361// Storage Merging by Symmetric Comparisons", in Susanne Albers and Tomasz362// Radzik, editors, Algorithms - ESA 2004, volume 3221 of Lecture Notes in363// Computer Science, pages 714-723. Springer, 2004.364//365// Let M = m-a and N = b-n. Wolog M < N.366// The recursion depth is bound by ceil(log(N+M)).367// The algorithm needs O(M*log(N/M + 1)) calls to data.Less.368// The algorithm needs O((M+N)*log(M)) calls to data.Swap.369//370// The paper gives O((M+N)*log(M)) as the number of assignments assuming a371// rotation algorithm which uses O(M+N+gcd(M+N)) assignments. The argumentation372// in the paper carries through for Swap operations, especially as the block373// swapping rotate uses only O(M+N) Swaps.374//375// symMerge assumes non-degenerate arguments: a < m && m < b.376// Having the caller check this condition eliminates many leaf recursion calls,377// which improves performance.378func symMerge(data Interface, a, m, b int) {379	// Avoid unnecessary recursions of symMerge380	// by direct insertion of data[a] into data[m:b]381	// if data[a:m] only contains one element.382	if m-a == 1 {383		// Use binary search to find the lowest index i384		// such that data[i] >= data[a] for m <= i < b.385		// Exit the search loop with i == b in case no such index exists.386		i := m387		j := b388		for i < j {389			h := int(uint(i+j) >> 1)390			if data.Less(h, a) {391				i = h + 1392			} else {393				j = h394			}395		}396		// Swap values until data[a] reaches the position before i.397		for k := a; k < i-1; k++ {398			data.Swap(k, k+1)399		}400		return401	}402 403	// Avoid unnecessary recursions of symMerge404	// by direct insertion of data[m] into data[a:m]405	// if data[m:b] only contains one element.406	if b-m == 1 {407		// Use binary search to find the lowest index i408		// such that data[i] > data[m] for a <= i < m.409		// Exit the search loop with i == m in case no such index exists.410		i := a411		j := m412		for i < j {413			h := int(uint(i+j) >> 1)414			if !data.Less(m, h) {415				i = h + 1416			} else {417				j = h418			}419		}420		// Swap values until data[m] reaches the position i.421		for k := m; k > i; k-- {422			data.Swap(k, k-1)423		}424		return425	}426 427	mid := int(uint(a+b) >> 1)428	n := mid + m429	var start, r int430	if m > mid {431		start = n - b432		r = mid433	} else {434		start = a435		r = m436	}437	p := n - 1438 439	for start < r {440		c := int(uint(start+r) >> 1)441		if !data.Less(p-c, c) {442			start = c + 1443		} else {444			r = c445		}446	}447 448	end := n - start449	if start < m && m < end {450		rotate(data, start, m, end)451	}452	if a < start && start < mid {453		symMerge(data, a, start, mid)454	}455	if mid < end && end < b {456		symMerge(data, mid, end, b)457	}458}459 460// rotate rotates two consecutive blocks u = data[a:m] and v = data[m:b] in data:461// Data of the form 'x u v y' is changed to 'x v u y'.462// rotate performs at most b-a many calls to data.Swap,463// and it assumes non-degenerate arguments: a < m && m < b.464func rotate(data Interface, a, m, b int) {465	i := m - a466	j := b - m467 468	for i != j {469		if i > j {470			swapRange(data, m-i, m, j)471			i -= j472		} else {473			swapRange(data, m-i, m+j-i, i)474			j -= i475		}476	}477	// i == j478	swapRange(data, m-i, m, i)479}480