/
sort.go
55 lines (47 loc) · 1.02 KB
/
sort.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
// Copyright (c) 2023, Intel Corporation.
// SPDX-License-Identifier: BSD-3-Clause
package huffman
import "unsafe"
func quickSortReverse(arr []uint32, left int, right int) {
for left < right {
if right-left < 16 {
insertReverseSort(arr[left : right+1])
break
} else {
pivot := arr[left]
i := left + 1
j := right
for i <= j {
if arr[i] < pivot && arr[j] > pivot {
arr[i], arr[j] = arr[j], arr[i]
}
if arr[i] >= pivot {
i++
}
if arr[j] <= pivot {
j--
}
}
arr[left], arr[j] = arr[j], arr[left]
if j-left < right-j {
quickSortReverse(arr, left, j-1)
left = j + 1
} else {
quickSortReverse(arr, j+1, right)
right = j - 1
}
}
}
}
func insertReverseSort(arr []uint32) {
for i := 1; i < len(arr); i++ {
for j := i; j > 0 && arr[j-1] < arr[j]; j-- {
arr[j-1], arr[j] = arr[j], arr[j-1]
}
}
}
func sortDecLitCounts(arr decLitCounts) {
// force type conversion
ilc := *(*[]uint32)(unsafe.Pointer(&arr))
quickSortReverse(ilc, 0, len(arr)-1)
}