FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
JavaScriptAlgorithms/Sorts/TimSort.js at master · manojsdeveloper/JavaScriptAlgorithms · GitHub
manojsdeveloper
/
JavaScriptAlgorithms
Public
forked from
TheAlgorithms/JavaScript
Notifications
You must be signed in to change notification settings
Fork
0
Star
0
Code
Pull requests
0
Actions
Projects
Security and quality
0
Insights
Additional navigation options
Code
Pull requests
Actions
Projects
Security and quality
Insights
Expand file tree
Breadcrumbs
JavaScriptAlgorithms
/
Sorts
/
TimSort.js
Copy path
More file actions
More file actions
Latest commit
History
History
History
113 lines (106 loc) · 2.97 KB
Breadcrumbs
JavaScriptAlgorithms
/
Sorts
/
TimSort.js
Copy path
File metadata and controls
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
}
Back
|
FazBrowse Home
|
New Git URL