вставки сортировки в Python не работает

Question

Я попытался следующий код для вставки рода в Python

a=[int(x) for x in input().split()] 
for i in range(1,len(a)): 
    temp=a[i] 
    for k in range (i,1,-1): 
     a[k]=a[k-1] 
     if a[k]<temp: 
      a[k]=temp 
      break 
print(a) 

вход: 6 4 3 2 5 8 1

выход: [6, 4, 4, 4 , 4, 5, 8]

Answer 1

Это не работает, потому что ваша реализация неисправна.
При попытке сдвинуть частично отсортированный список, вы перезаписываете существующие номера, назначая a[k] = a[k-1] - но где же прежнее значение a[k]?

Определенное базовое решение (но не на месте, так как определено исходное определение в одном списке) может выглядеть так.

inp = '1 4 6 3 1 6 3 5 8 1' 

# 'a' is the input list 
a = [int(x) for x in inp.split()] 
# 'r' is the sorted list 
r = [] 
# In the original descriptions, insertion sort operates 
# on a single list while iterating over it. However, this 
# may lead to major failurs, thus you better carry the 
# sorted list in a separate variable if memory is not 
# a limiting factor (which it can hardly be for lists that 
# are typed in by the user). 

for e in a: 
    if not len(r): 
     # The first item is the inialization 
     r.append(e) 
    else: 
     # For each subsequent item, find the spot in 'r' 
     # where it has to go. 
     idx = 0 
     while idx < len(r) and r[idx] < e: idx += 1 
     # We are lazy and use insert() instead of manually 
     # extending the list by 1 place and copying over 
     # all subsequent items [idx:] to the right 
     r.insert(idx, e) 
print(r)