Python/sorts/tim_sort.py at master · gio-puter/Python · GitHub

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
defbinary_search(lst, item, start, end):
ifstart==end:
returnstartiflst[start] >itemelsestart+1
ifstart>end:
returnstart

mid= (start+end) //2
iflst[mid] <item:
returnbinary_search(lst, item, mid+1, end)
eliflst[mid] >item:
returnbinary_search(lst, item, start, mid-1)
else:
returnmid


definsertion_sort(lst):
length=len(lst)

forindexinrange(1, length):
value=lst[index]
pos=binary_search(lst, value, 0, index-1)
lst=lst[:pos] + [value] +lst[pos:index] +lst[index+1 :]

returnlst


defmerge(left, right):
ifnotleft:
returnright

ifnotright:
returnleft

ifleft[0] <right[0]:
return [left[0], *merge(left[1:], right)]

return [right[0], *merge(left, right[1:])]


deftim_sort(lst):
"""
 >>> tim_sort("Python")
 ['P', 'h', 'n', 'o', 't', 'y']
 >>> tim_sort((1.1, 1, 0, -1, -1.1))
 [-1.1, -1, 0, 1, 1.1]
 >>> tim_sort(list(reversed(list(range(7)))))
 [0, 1, 2, 3, 4, 5, 6]
 >>> tim_sort([3, 2, 1]) == insertion_sort([3, 2, 1])
 True
 >>> tim_sort([3, 2, 1]) == sorted([3, 2, 1])
 True
 """
length=len(lst)
runs, sorted_runs= [], []
new_run= [lst[0]]
sorted_array= []
i=1
whilei<length:
iflst[i] <lst[i-1]:
runs.append(new_run)
new_run= [lst[i]]
else:
new_run.append(lst[i])
i+=1
runs.append(new_run)

forruninruns:
sorted_runs.append(insertion_sort(run))
forruninsorted_runs:
sorted_array=merge(sorted_array, run)

returnsorted_array


defmain():
lst= [5, 9, 10, 3, -4, 5, 178, 92, 46, -18, 0, 7]
sorted_lst=tim_sort(lst)
print(sorted_lst)


if__name__=="__main__":
main()
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
defbinary_search(lst, item, start, end):
ifstart==end:
returnstartiflst[start] >itemelsestart+1
ifstart>end:
returnstart

mid= (start+end) //2
iflst[mid] <item:
returnbinary_search(lst, item, mid+1, end)
eliflst[mid] >item:
returnbinary_search(lst, item, start, mid-1)
else:
returnmid


definsertion_sort(lst):
length=len(lst)

forindexinrange(1, length):
value=lst[index]
pos=binary_search(lst, value, 0, index-1)
lst=lst[:pos] + [value] +lst[pos:index] +lst[index+1 :]

returnlst


defmerge(left, right):
ifnotleft:
returnright

ifnotright:
returnleft

ifleft[0] <right[0]:
return [left[0], *merge(left[1:], right)]

return [right[0], *merge(left, right[1:])]


deftim_sort(lst):
"""
 >>> tim_sort("Python")
 ['P', 'h', 'n', 'o', 't', 'y']
 >>> tim_sort((1.1, 1, 0, -1, -1.1))
 [-1.1, -1, 0, 1, 1.1]
 >>> tim_sort(list(reversed(list(range(7)))))
 [0, 1, 2, 3, 4, 5, 6]
 >>> tim_sort([3, 2, 1]) == insertion_sort([3, 2, 1])
 True
 >>> tim_sort([3, 2, 1]) == sorted([3, 2, 1])
 True
 """
length=len(lst)
runs, sorted_runs= [], []
new_run= [lst[0]]
sorted_array= []
i=1
whilei<length:
iflst[i] <lst[i-1]:
runs.append(new_run)
new_run= [lst[i]]
else:
new_run.append(lst[i])
i+=1
runs.append(new_run)

forruninruns:
sorted_runs.append(insertion_sort(run))
forruninsorted_runs:
sorted_array=merge(sorted_array, run)

returnsorted_array


defmain():
lst= [5, 9, 10, 3, -4, 5, 178, 92, 46, -18, 0, 7]
sorted_lst=tim_sort(lst)
print(sorted_lst)


if__name__=="__main__":
main()
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
defbinary_search(lst, item, start, end):
ifstart==end:
returnstartiflst[start] >itemelsestart+1
ifstart>end:
returnstart

mid= (start+end) //2
iflst[mid] <item:
returnbinary_search(lst, item, mid+1, end)
eliflst[mid] >item:
returnbinary_search(lst, item, start, mid-1)
else:
returnmid


definsertion_sort(lst):
length=len(lst)

forindexinrange(1, length):
value=lst[index]
pos=binary_search(lst, value, 0, index-1)
lst=lst[:pos] + [value] +lst[pos:index] +lst[index+1 :]

returnlst


defmerge(left, right):
ifnotleft:
returnright

ifnotright:
returnleft

ifleft[0] <right[0]:
return [left[0], *merge(left[1:], right)]

return [right[0], *merge(left, right[1:])]


deftim_sort(lst):
"""
 >>> tim_sort("Python")
 ['P', 'h', 'n', 'o', 't', 'y']
 >>> tim_sort((1.1, 1, 0, -1, -1.1))
 [-1.1, -1, 0, 1, 1.1]
 >>> tim_sort(list(reversed(list(range(7)))))
 [0, 1, 2, 3, 4, 5, 6]
 >>> tim_sort([3, 2, 1]) == insertion_sort([3, 2, 1])
 True
 >>> tim_sort([3, 2, 1]) == sorted([3, 2, 1])
 True
 """
length=len(lst)
runs, sorted_runs= [], []
new_run= [lst[0]]
sorted_array= []
i=1
whilei<length:
iflst[i] <lst[i-1]:
runs.append(new_run)
new_run= [lst[i]]
else:
new_run.append(lst[i])
i+=1
runs.append(new_run)

forruninruns:
sorted_runs.append(insertion_sort(run))
forruninsorted_runs:
sorted_array=merge(sorted_array, run)

returnsorted_array


defmain():
lst= [5, 9, 10, 3, -4, 5, 178, 92, 46, -18, 0, 7]
sorted_lst=tim_sort(lst)
print(sorted_lst)


if__name__=="__main__":
main()
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
defbinary_search(lst, item, start, end):
ifstart==end:
returnstartiflst[start] >itemelsestart+1
ifstart>end:
returnstart

mid= (start+end) //2
iflst[mid] <item:
returnbinary_search(lst, item, mid+1, end)
eliflst[mid] >item:
returnbinary_search(lst, item, start, mid-1)
else:
returnmid


definsertion_sort(lst):
length=len(lst)

forindexinrange(1, length):
value=lst[index]
pos=binary_search(lst, value, 0, index-1)
lst=lst[:pos] + [value] +lst[pos:index] +lst[index+1 :]

returnlst


defmerge(left, right):
ifnotleft:
returnright

ifnotright:
returnleft

ifleft[0] <right[0]:
return [left[0], *merge(left[1:], right)]

return [right[0], *merge(left, right[1:])]


deftim_sort(lst):
"""
 >>> tim_sort("Python")
 ['P', 'h', 'n', 'o', 't', 'y']
 >>> tim_sort((1.1, 1, 0, -1, -1.1))
 [-1.1, -1, 0, 1, 1.1]
 >>> tim_sort(list(reversed(list(range(7)))))
 [0, 1, 2, 3, 4, 5, 6]
 >>> tim_sort([3, 2, 1]) == insertion_sort([3, 2, 1])
 True
 >>> tim_sort([3, 2, 1]) == sorted([3, 2, 1])
 True
 """
length=len(lst)
runs, sorted_runs= [], []
new_run= [lst[0]]
sorted_array= []
i=1
whilei<length:
iflst[i] <lst[i-1]:
runs.append(new_run)
new_run= [lst[i]]
else:
new_run.append(lst[i])
i+=1
runs.append(new_run)

forruninruns:
sorted_runs.append(insertion_sort(run))
forruninsorted_runs:
sorted_array=merge(sorted_array, run)

returnsorted_array


defmain():
lst= [5, 9, 10, 3, -4, 5, 178, 92, 46, -18, 0, 7]
sorted_lst=tim_sort(lst)
print(sorted_lst)


if__name__=="__main__":
main()
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
defbinary_search(lst, item, start, end):
ifstart==end:
returnstartiflst[start] >itemelsestart+1
ifstart>end:
returnstart

mid= (start+end) //2
iflst[mid] <item:
returnbinary_search(lst, item, mid+1, end)
eliflst[mid] >item:
returnbinary_search(lst, item, start, mid-1)
else:
returnmid


definsertion_sort(lst):
length=len(lst)

forindexinrange(1, length):
value=lst[index]
pos=binary_search(lst, value, 0, index-1)
lst=lst[:pos] + [value] +lst[pos:index] +lst[index+1 :]

returnlst


defmerge(left, right):
ifnotleft:
returnright

ifnotright:
returnleft

ifleft[0] <right[0]:
return [left[0], *merge(left[1:], right)]

return [right[0], *merge(left, right[1:])]


deftim_sort(lst):
"""
 >>> tim_sort("Python")
 ['P', 'h', 'n', 'o', 't', 'y']
 >>> tim_sort((1.1, 1, 0, -1, -1.1))
 [-1.1, -1, 0, 1, 1.1]
 >>> tim_sort(list(reversed(list(range(7)))))
 [0, 1, 2, 3, 4, 5, 6]
 >>> tim_sort([3, 2, 1]) == insertion_sort([3, 2, 1])
 True
 >>> tim_sort([3, 2, 1]) == sorted([3, 2, 1])
 True
 """
length=len(lst)
runs, sorted_runs= [], []
new_run= [lst[0]]
sorted_array= []
i=1
whilei<length:
iflst[i] <lst[i-1]:
runs.append(new_run)
new_run= [lst[i]]
else:
new_run.append(lst[i])
i+=1
runs.append(new_run)

forruninruns:
sorted_runs.append(insertion_sort(run))
forruninsorted_runs:
sorted_array=merge(sorted_array, run)

returnsorted_array


defmain():
lst= [5, 9, 10, 3, -4, 5, 178, 92, 46, -18, 0, 7]
sorted_lst=tim_sort(lst)
print(sorted_lst)


if__name__=="__main__":
main()
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
defbinary_search(lst, item, start, end):
ifstart==end:
returnstartiflst[start] >itemelsestart+1
ifstart>end:
returnstart

mid= (start+end) //2
iflst[mid] <item:
returnbinary_search(lst, item, mid+1, end)
eliflst[mid] >item:
returnbinary_search(lst, item, start, mid-1)
else:
returnmid


definsertion_sort(lst):
length=len(lst)

forindexinrange(1, length):
value=lst[index]
pos=binary_search(lst, value, 0, index-1)
lst=lst[:pos] + [value] +lst[pos:index] +lst[index+1 :]

returnlst


defmerge(left, right):
ifnotleft:
returnright

ifnotright:
returnleft

ifleft[0] <right[0]:
return [left[0], *merge(left[1:], right)]

return [right[0], *merge(left, right[1:])]


deftim_sort(lst):
"""
 >>> tim_sort("Python")
 ['P', 'h', 'n', 'o', 't', 'y']
 >>> tim_sort((1.1, 1, 0, -1, -1.1))
 [-1.1, -1, 0, 1, 1.1]
 >>> tim_sort(list(reversed(list(range(7)))))
 [0, 1, 2, 3, 4, 5, 6]
 >>> tim_sort([3, 2, 1]) == insertion_sort([3, 2, 1])
 True
 >>> tim_sort([3, 2, 1]) == sorted([3, 2, 1])
 True
 """
length=len(lst)
runs, sorted_runs= [], []
new_run= [lst[0]]
sorted_array= []
i=1
whilei<length:
iflst[i] <lst[i-1]:
runs.append(new_run)
new_run= [lst[i]]
else:
new_run.append(lst[i])
i+=1
runs.append(new_run)

forruninruns:
sorted_runs.append(insertion_sort(run))
forruninsorted_runs:
sorted_array=merge(sorted_array, run)

returnsorted_array


defmain():
lst= [5, 9, 10, 3, -4, 5, 178, 92, 46, -18, 0, 7]
sorted_lst=tim_sort(lst)
print(sorted_lst)


if__name__=="__main__":
main()
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
defbinary_search(lst, item, start, end):
ifstart==end:
returnstartiflst[start] >itemelsestart+1
ifstart>end:
returnstart

mid= (start+end) //2
iflst[mid] <item:
returnbinary_search(lst, item, mid+1, end)
eliflst[mid] >item:
returnbinary_search(lst, item, start, mid-1)
else:
returnmid


definsertion_sort(lst):
length=len(lst)

forindexinrange(1, length):
value=lst[index]
pos=binary_search(lst, value, 0, index-1)
lst=lst[:pos] + [value] +lst[pos:index] +lst[index+1 :]

returnlst


defmerge(left, right):
ifnotleft:
returnright

ifnotright:
returnleft

ifleft[0] <right[0]:
return [left[0], *merge(left[1:], right)]

return [right[0], *merge(left, right[1:])]


deftim_sort(lst):
"""
 >>> tim_sort("Python")
 ['P', 'h', 'n', 'o', 't', 'y']
 >>> tim_sort((1.1, 1, 0, -1, -1.1))
 [-1.1, -1, 0, 1, 1.1]
 >>> tim_sort(list(reversed(list(range(7)))))
 [0, 1, 2, 3, 4, 5, 6]
 >>> tim_sort([3, 2, 1]) == insertion_sort([3, 2, 1])
 True
 >>> tim_sort([3, 2, 1]) == sorted([3, 2, 1])
 True
 """
length=len(lst)
runs, sorted_runs= [], []
new_run= [lst[0]]
sorted_array= []
i=1
whilei<length:
iflst[i] <lst[i-1]:
runs.append(new_run)
new_run= [lst[i]]
else:
new_run.append(lst[i])
i+=1
runs.append(new_run)

forruninruns:
sorted_runs.append(insertion_sort(run))
forruninsorted_runs:
sorted_array=merge(sorted_array, run)

returnsorted_array


defmain():
lst= [5, 9, 10, 3, -4, 5, 178, 92, 46, -18, 0, 7]
sorted_lst=tim_sort(lst)
print(sorted_lst)


if__name__=="__main__":
main()
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
defbinary_search(lst, item, start, end):
ifstart==end:
returnstartiflst[start] >itemelsestart+1
ifstart>end:
returnstart

mid= (start+end) //2
iflst[mid] <item:
returnbinary_search(lst, item, mid+1, end)
eliflst[mid] >item:
returnbinary_search(lst, item, start, mid-1)
else:
returnmid


definsertion_sort(lst):
length=len(lst)

forindexinrange(1, length):
value=lst[index]
pos=binary_search(lst, value, 0, index-1)
lst=lst[:pos] + [value] +lst[pos:index] +lst[index+1 :]

returnlst


defmerge(left, right):
ifnotleft:
returnright

ifnotright:
returnleft

ifleft[0] <right[0]:
return [left[0], *merge(left[1:], right)]

return [right[0], *merge(left, right[1:])]


deftim_sort(lst):
"""
 >>> tim_sort("Python")
 ['P', 'h', 'n', 'o', 't', 'y']
 >>> tim_sort((1.1, 1, 0, -1, -1.1))
 [-1.1, -1, 0, 1, 1.1]
 >>> tim_sort(list(reversed(list(range(7)))))
 [0, 1, 2, 3, 4, 5, 6]
 >>> tim_sort([3, 2, 1]) == insertion_sort([3, 2, 1])
 True
 >>> tim_sort([3, 2, 1]) == sorted([3, 2, 1])
 True
 """
length=len(lst)
runs, sorted_runs= [], []
new_run= [lst[0]]
sorted_array= []
i=1
whilei<length:
iflst[i] <lst[i-1]:
runs.append(new_run)
new_run= [lst[i]]
else:
new_run.append(lst[i])
i+=1
runs.append(new_run)

forruninruns:
sorted_runs.append(insertion_sort(run))
forruninsorted_runs:
sorted_array=merge(sorted_array, run)

returnsorted_array


defmain():
lst= [5, 9, 10, 3, -4, 5, 178, 92, 46, -18, 0, 7]
sorted_lst=tim_sort(lst)
print(sorted_lst)


if__name__=="__main__":
main()