FilesExpand file tree

 master

/

TimSort.py

Copy path

BlameMore file actions

BlameMore file actions

Latest commit

 

History

History

History

41 lines (35 loc) · 1.43 KB

 master

/

TimSort.py

Top

File metadata and controls

• Code
• Blame

41 lines (35 loc) · 1.43 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

def timsort(array):

min_run = 32

n = len(array)

# Start by slicing and sorting small portions of the

# input array. The size of these slices is defined by

# your `min_run` size.

for i in range(0, n, min_run):

insertion_sort(array, i, min((i + min_run - 1), n - 1))

# Now you can start merging the sorted slices.

# Start from `min_run`, doubling the size on

# each iteration until you surpass the length of

# the array.

size = min_run

while size < n:

# Determine the arrays that will

# be merged together

for start in range(0, n, size * 2):

# Compute the `midpoint` (where the first array ends

# and the second starts) and the `endpoint` (where

# the second array ends)

midpoint = start + size - 1

end = min((start + size * 2 - 1), (n-1))

# Merge the two subarrays.

# The `left` array should go from `start` to

# `midpoint + 1`, while the `right` array should

# go from `midpoint + 1` to `end + 1`.

merged_array = merge(

left=array[start:midpoint + 1],

right=array[midpoint + 1:end + 1])

# Finally, put the merged array back into

# your array

array[start:start + len(merged_array)] = merged_array

# Each iteration should double the size of your arrays

size *= 2

return array