Chapter $5-$Programming Project: Implement a function that takes in two sorted lists and merges them into one list, the new list must be sorted. The function MUST run in O$($m$+$n$),$ where m is the length of list $1$ and n the length of list $2.$ In other words, the function cannot do more than one pass on list $1$ and list $2.$

Use the base code given and write it in python:

# Assignment: Programming Project $3$

def merge$\_$sorted$\_$lists$($list$1,$ list$2)$:

$"""$

This function merges two sorted lists into one sorted list.

Parameters:

list$1($list$)$: The first sorted list.

list$2($list$)$: The second sorted list.

Returns:

list: A sorted list that contains all elements from list$1$ and list$2.$

$"""$

merged$\_$list $=[]$

# WRITE YOUR CODE HERE

# Hint:

# $1.$ Keep two pointers, each initially pointing to the start of list$1$ and list$2.$

# $2.$ Compare the elements pointed by the pointers and choose the smaller one to append to the 'merged$\_$list'.

# $3.$ Increment the pointer of the list from which an element is chosen.

# $4.$ If one list gets exhausted, append all remaining elements from the other list to 'merged$\_$list'.

return merged$\_$list

if $\_\_$name$\_\_==\text{'}\_\_$main$\_\_\text{'}$:

list$1=[1,3,5,7,9]$

list$2=[2,4,6,8,10]$

print$($merge$\_$sorted$\_$lists$($list$1,$ list$2))$ # $[1,2,3,4,5,6,7,8,9,10]$

list$3=[1,3,5,7]$

list$4=[2,4,6,8,9,10]$

print$($merge$\_$sorted$\_$lists$($list$3,$ list$4))$ # $[1,2,3,4,5,6,7,8,9,10]$