CareerCup

l1=[1,3,4,12,24,45]
l2=[1,2,3,4,5,6,7,None,None,None,None,None,None]
def merge_into_l2(l1,l2):
    i=len(l1)-1
    j=len(l2)-len(l1)-1
    k=len(l2)-1
    while(i>=0 and j>=0 and k>=0):
        if(l1[i]>=l2[j]):
            l2[k]=l1[i]
            i-=1
            k-=1
        else:
            l2[k]=l2[j]
            j-=1
            k-=1
    return l2
print(merge_into_l2(l1,l2))
Thank You
-Nikhilkumar Kekan

I would do something like this,

public static void main(String[] args) {
    
    int[] a = {1, 2, 3, 4, 5};
    int[] b = {1, 1, 2, 2, 3, 3, 4, 4, 5};
    int[] c = new int[a.length + b.length];
    
    int i = 0, j = 0, end = 0;
    while (i < a.length && j < b.length)
        c[end++] = (a[i] <= b[j]) ? a[i++] : b[j++];
    while (i < a.length)
        c[end++] = a[i++];
    while (j < b.length)
        c[end++] = b[j++];
    
    System.out.println(Arrays.toString(c));
}

just so that I can avoid nulls & unnecessary if conditions
while takes just as much time even when split

public void merge(int[] nums1, int m, int[] nums2, int n) {
		int index2 = nums2.length - 1;
		int index1 = nums1.length - nums2.length - 1;

		for (int i = nums1.length - 1; i >= 0; i--) {
			nums1[i] = (index2 < 0 || (index1 >= 0 && nums1[index1] >= nums2[index2])) ? nums1[index1--]
					: nums2[index2--];
		}
	}

def merge(X, Y, m, n):
k = m + n + 1
while (m >= 0 and n >= 0):
if (X[m] > Y[n]):
X[k] = X[m]
k -= 1
m -= 1
else:
X[k] = Y[n]
k -= 1
n -= 1
while (n >= 0):
X[k] = Y[n]
k -= 1
n -= 1
merge(l2,l1,len(l2),len(l1))

def merge(X, Y, m, n):
    k = m + n + 1
    while (m >= 0 and n >= 0):
        if (X[m] > Y[n]):
            X[k] = X[m]
            k -= 1
            m -= 1
        else:
            X[k] = Y[n]
            k -= 1
            n -= 1
    while (n >= 0):
        X[k] = Y[n]
        k -= 1
        n -= 1
merge(l2,l1,len(l2),len(l1))

var array = [1,2,3,4,5,6]
let k = 2
for i in 0 ..< k {
for j in i ..< (array.count - 1 + i) {
let temp = array[array.count - 2 + i]
array[array.count - 2 + i] = array[j]
array[j] = temp
}
}

var array = [1,2,3,4,5,6]
let k = 2
for i in 0 ..< k {
for j in i ..< (array.count - 1 + i) {
let temp = array[array.count - 2 + i]
array[array.count - 2 + i] = array[j]
array[j] = temp
}
}

var array = [1,2,3,4,5,6]
		let k = 2
		for i in 0 ..< k {
			for j in i ..< (array.count - 1 + i) {
				let temp = array[array.count - 2 + i]
				array[array.count - 2 + i] = array[j]
				array[j] = temp
			}
		}

var array = [1,2,3,4,5,6]
		let k = 2
		for i in 0 ..< k {
			for j in i ..< (array.count - 1 + i) {
				let temp = array[array.count - 2 + i]
				array[array.count - 2 + i] = array[j]
				array[j] = temp
			}
		}

var array = [1,2,3,4,5,6]
let k = 2
for i in 0 ..< k {
for j in i ..< (array.count - 1 + i) {
let temp = array[array.count - 2 + i]
array[array.count - 2 + i] = array[j]
array[j] = temp
}
}

def merge(X, Y, m, n):
k = m + n + 1
while (m >= 0 and n >= 0):
if (X[m] > Y[n]):
X[k] = X[m]
k -= 1
m -= 1
else:
X[k] = Y[n]
k -= 1
n -= 1
while (n >= 0):
X[k] = Y[n]
k -= 1
n -= 1
merge(l2,l1,len(l2),len(l1))

var array = [1,2,3,4,5,6]
let k = 2
for i in 0 ..< k {
for j in i ..< (array.count - 1 + i) {
let temp = array[array.count - 2 + i]
array[array.count - 2 + i] = array[j]
array[j] = temp
}
}

func shiftLastTwoElementInArray(_ array: [Int]) {
var array = array
let k = 2
for i in 0 ..< k {
for j in i ..< (array.count - 1 + i) {
let temp = array[array.count - 2 + i]
array[array.count - 2 + i] = array[j]
array[j] = temp
}
}
}

l1=[1,2,3,4,7,8,8,9]
l2=[1,3,6,7,None,7,None,None,None]
for j in range(len(l2)):
for i in range(len(l1)):

if l2[j] is not None and l2[j]>= l1[len(l1)-1] :
l1.append(l2[j])

break
if l2[j] is not None and l2[j]<= l1[i] :
l1.insert(i,l2[j])

break
print(l1)

l1=[1,2,3,4,7,8,8,9] 
l2=[1,3,6,7,None,7,None,None,None]
for j in range(len(l2)):
    for i in range(len(l1)):
        #print("i is " + str(i) +" j is " + str(j))
        if l2[j] is not None and l2[j]>= l1[len(l1)-1] :
            l1.append(l2[j])
            #print(l1)
            break
        if l2[j] is not None and l2[j]<= l1[i] :
            l1.insert(i,l2[j])
            #print(l1)
            break
print(l1)

l1=[1,2,3,4,7,8,8,9] 
l2=[1,3,6,7,None,7,None,None,None]
for j in range(len(l2)):
    for i in range(len(l1)):
        #print("i is " + str(i) +" j is " + str(j))
        if l2[j] is not None and l2[j]>= l1[len(l1)-1] :
            l1.append(l2[j])
            #print(l1)
            break
        if l2[j] is not None and l2[j]<= l1[i] :
            l1.insert(i,l2[j])
            #print(l1)
            break
print(l1)

testcode

l1=[1,2,3,4,7,8,8,9] 
l2=[1,3,6,7,None,7,None,None,None]
for j in range(len(l2)):
    for i in range(len(l1)):
        #print("i is " + str(i) +" j is " + str(j))
        if l2[j] is not None and l2[j]>= l1[len(l1)-1] :
            l1.append(l2[j])
            #print(l1)
            break
        if l2[j] is not None and l2[j]<= l1[i] :
            l1.insert(i,l2[j])
            #print(l1)
            break
print(l1)

def merge_lists(l1, l2):
    i, j = 0, 0
    final = []
    while (i < len(l1) and j < len(l2)):
        if l1[i] == l2[j]:
            final.append(l1[i])
            final.append(l2[j])
            i += 1 
            j += 1
        elif l1[i] < l2[j]:
            final.append(l1[i])
            i += 1
        else:
            final.append(l2[j])
            j += 1
    if i < len(l1):
        final.extend(l1[i:])
    elif j < len(l2):
        final.extend(l2[j:])
    return final

A very easy solution in O(n)
since l2 already has space to accomodate l1, lets push all l2 elements to its end, keeping l2's front empty.
shiftL2ToEnd() in O(n) time
Now use 2 pointer approach to fill up l1 in l2's blank space . for cases where the pointer shifts to l2, we can empty that space in l2 and move it to front.

merge method from mergesort