Łączenie wyników dwóch posortowanych tablic

Załóżmy, że mamy jedną ciągłą tablicę (100 elementową) wypełnioną losowymi liczbami, którą podzielimy następnie na dwie równe części po 50 elementów. Następnie wykonamy na tych dwóch tablicach QuickSort'a. Pytania jakie się teraz mi nasuwają to:

1) Jaką złożoność osiągnie algorytm QuickSort dla tak przygotowanych danych po wywołaniu jego na całej tablicy?
2) Jeśli złożoność > liniowa to czy istnieje algorytm, który zrobi to liniowo bez tworzenia pomocniczej tablicy?

1) n**2, ew. nlogn, zależnie od implementacji quicksorta
2) Czyli liniowe scalanie z O(1) pamięci działające nawet jeśli mamy perfidny aliasing? Wymyśl, będziesz sławny i bogaty.

Nie no... tablice dwie mamy posortowane, chodzi o ich scalenie bez tworzenia nowej tablicy i tak, żeby wynik ostateczny był posortowany :)

Poprawiłem.