Interclasarea parcurge cele două liste simultan, alegând mereu cea mai mică valoare disponibilă și adăugând-o în rezultat. Complexitate O(n+m), mult mai bună decât sortarea listei concatenate O((n+m)·log(n+m)).
python.py
def interclaseaza(a, b):
rez = []
i = j = 0
while i < len(a) and j < len(b):
if a[i] <= b[j]:
rez.append(a[i]); i += 1
else:
rez.append(b[j]); __
rez.extend(a[i:]); rez.extend(b[j:])
return rez
print(interclaseaza([1, 4, 7], [2, 3, 8])) # [1, 2, 3, 4, 7, 8]
Interclasarea e baza sortării prin interclasare (merge sort, modulul 2.19).
Sfaturi & Bune Practici Didactice
:::tip
La calculul recursiv al șirului Fibonacci sau factorialului, verifică valorile de intrare pentru n <= 0 pentru a preveni apeluri infinite!