[DSAL] Frage zu H15

[SubZer0]

Hi,

habe eine Frage zu H15. Dazu am Besten ein Beispiel:

Eingabe: T[n] = {2,3,0,1} (vorsortiert von 0 bis m-1 und von m bis n-1)
=> n = 4 => m = 2

Ausgabe soll sein: A[n] = {0,1,2,3} (T[n] sortiert)

Sei c = a+b-m+1

Man bestimme a,b mit 0<= a <= m-1 und m<= b <= n-1 und a+b=n+-1 sodass man T[0...a] und T[m...b-1] in A[0...c] mischen kann und T[a+1...m-1] und T[b...n-1] in A[c...n-1] mischen kann sodass A[n] rauskommt.

Dadurch dass b höchstens n-1 sein kann, landet das letzte Element von T[n] immer im hinteren Teil von A[n], im vorderen Teil landet jedoch in jedem Fall das erste Element von T[n] (wegen a>=0). Damit ist das Ausgabearray im konkreten Fall für alle möglichen Belegungen von a und b nicht sortiert (da 2 vor 1 steht). Daraus folgt, dass ein solches Paar a,b nicht existieren kann.

Wo ist der Denkfehler?

mfg & thx 4 help