FilesExpand file tree

 master

/

TimSort.js

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

113 lines (106 loc) · 2.97 KB

 master

/

TimSort.js

Copy path

Top

File metadata and controls

• Code
• Blame

113 lines (106 loc) · 2.97 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

/**

* @function Timsort is a hybrid stable sorting algorithm, derived from merge sort and insertion sort,

* designed to perform well on many kinds of real-world data.

* It was implemented by Tim Peters in 2002 for use in the Python programming language.

* It is also used to sort arrays of non-primitive type in Java SE 7,

* on the Android platform, in GNU Octave, on V8, Swift and Rust.

* 1) It sorts small partitions using Insertion Sort.

* 2) Merges the partition using Merge Sort.

* @see [Timsort](https://en.wikipedia.org/wiki/Timsort)

* @param {Array} array

*/

const Timsort = (array) => {

// Default size of a partition

const RUN = 32

const n = array.length

// Sorting the partitions using Insertion Sort

for (let i = 0; i < n; i += RUN) {

InsertionSort(array, i, Math.min(i + RUN - 1, n - 1))

}

for (let size = RUN; size < n; size *= 2) {

for (let left = 0; left < n; left += 2 * size) {

const mid = left + size - 1

const right = Math.min(left + 2 * size - 1, n - 1)

Merge(array, left, mid, right)

}

}

return array

}

/**

* @function performs insertion sort on the partition

* @param {Array} array array to be sorted

* @param {Number} left left index of partition

* @param {Number} right right index of partition

*/

const InsertionSort = (array, left, right) => {

for (let i = left + 1; i <= right; i++) {

const key = array[i]

let j = i - 1

while (j >= left && array[j] > key) {

array[j + 1] = array[j]

j--

}

array[j + 1] = key

}

}

/**

* @function merges two sorted partitions

* @param {Array} array array to be sorted

* @param {Number} left left index of partition

* @param {Number} mid mid index of partition

* @param {Number} right right index of partition

*/

const Merge = (array, left, mid, right) => {

if (mid >= right) return

const len1 = mid - left + 1

const len2 = right - mid

const larr = Array(len1)

const rarr = Array(len2)

for (let i = 0; i < len1; i++) {

larr[i] = array[left + i]

}

for (let i = 0; i < len2; i++) {

rarr[i] = array[mid + 1 + i]

}

let i = 0; let j = 0; let k = left

while (i < larr.length && j < rarr.length) {

if (larr[i] < rarr[j]) {

array[k++] = larr[i++]

} else {

array[k++] = rarr[j++]

}

}

while (i < larr.length) {

array[k++] = larr[i++]

}

while (j < rarr.length) {

array[k++] = rarr[j++]

}

}

/**

* @example Test of Timsort functions.

* Data is randomly generated.

* Return "RIGHT" if it works as expected,

* otherwise "FAULTY"

*/

const demo = () => {

const size = 1000000

const data = Array(size)

for (let i = 0; i < size; i++) {

data[i] = Math.random() * Number.MAX_SAFE_INTEGER

}

const isSorted = function (array) {

const n = array.length

for (let i = 0; i < n - 1; i++) {

if (array[i] > array[i + 1]) return false

}

return true

}

Timsort(data)

if (isSorted(data)) {

return 'RIGHT'

} else {

return 'FAULTY'

}

}

export { Timsort, demo }