La complessità che puoi ambire è O(\log G). Riponiamo il problema come segue:
trovare il G-esimo minore dati due array preordinati di dimensione uguale a N (in realtà quest’ultimo aspetto non ha importanza).
[spoiler]Propongo un algoritmo divide et impera , e per farlo osserviamo un dato cruciale:
Osservazione: siano i e j due indici del primo e del secondo vettore (banalmente j è nella forma j = N + j', quindi WLOG tratteremo i due array separatamente). Se A[i]<B[j] \implies A[k] < B[j], \quad k = 0,1,\dots,i e analogamente \implies A[i] < B[l], \quad l = j, j+1,\dots, |B|-1 . Ciò significa che, se i non è l’indice adatto, devo cercarlo o tra i succcessori di A[i] (A[i] escluso), o tra i predecessori di B[j] (incluso). Considerazioni opposte se vale il confronto opposto.
L’idea è: supponiamo di prendere inizialmente due valori di i e j pari a G/2. In questo modo gestiremo due subarray che complessivamente avranno G/2 elementi. Se A[i] < B[j], vorrà dire che l’elemento G potrebbe trovarsi o dopo A[i] o prima di B[j]. A questo punto, osserviamo che gli elementi prima di A[i] (A[i] incluso) saranno “tolti”, di conseguenza vanno anch’essi tolti da G.
Quindi, se avessi una funzione findG^{th}(A, B, sz_A, sz_B, G) la dovrei richiamare, dopo il confronto, con questi valori: findG^{th}(A + i, B, sz_A - i + 1, sz_B - j, G - j).
Considerazione analoghe se il confronto è opposto.
Un caso base è quando G = 1, infatti devi soltanto capire qual è il minimo tra i due array, ovvero tra i loro primi elementi. Un altro caso base è quando un array è vuoto, in tal caso devi prendere il G-esimo elemento dell’altro vettore.[/spoiler]
Lascio a te il compito di sistemare gli altri dettagli implementativi, e anche la rogna degli array 0-based o 1-based (che mi ha dato personalmente parecchi grattacapi). Comunuque, è ovvio il perché l’algoritmo proposto funziona e ha complessità O(\log k)