<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 Sorting exercises
Step1:  Fill in the code for the functions below. main() is already set up
to call the functions with a few different inputs,
printing 'OK' when each function is correct.
The starter code for each function includes a 'return'
which is just a placeholder for your code.
A. front_x
Given a list of strings, return a list with the strings
in sorted order, except group all the strings that begin with 'x' first.
e.g. ['mix', 'xyz', 'apple', 'xanadu', 'aardvark'] yields
['xanadu', 'xyz', 'aardvark', 'apple', 'mix']
Step2:  B. sort_last
Given a list of non-empty tuples, return a list sorted in increasing
order by the last element in each tuple.
e.g. [(1, 7), (1, 3), (3, 4, 5), (2, 2)] yields
[(2, 2), (1, 3), (3, 4, 5), (1, 7)]
Step3:  C. linear_merge
Given two lists sorted in increasing order, create and return a merged
list of all the elements in sorted order. You may modify the passed in lists.
Ideally, the solution should work in "linear" time, making a single
pass of both lists.
<ASSISTANT_TASK:>
Python Code:
# Provided simple test() function used in main() to print
# what each function returns vs. what it's supposed to return.
def test(got, expected):
    if got == expected:
        prefix = ' OK '
    else:
        prefix = '  X '
    print '%s got: %s expected: %s' % (prefix, repr(got), repr(expected))
Explanation: Sorting exercises
End of explanation
def front_x(words):
    # +++your code here+++
    return
test(front_x(['bbb', 'ccc', 'axx', 'xzz', 'xaa']),
   ['xaa', 'xzz', 'axx', 'bbb', 'ccc'])
test(front_x(['ccc', 'bbb', 'aaa', 'xcc', 'xaa']),
   ['xaa', 'xcc', 'aaa', 'bbb', 'ccc'])
test(front_x(['mix', 'xyz', 'apple', 'xanadu', 'aardvark']),
   ['xanadu', 'xyz', 'aardvark', 'apple', 'mix'])
Explanation: Fill in the code for the functions below. main() is already set up
to call the functions with a few different inputs,
printing 'OK' when each function is correct.
The starter code for each function includes a 'return'
which is just a placeholder for your code.
A. front_x
Given a list of strings, return a list with the strings
in sorted order, except group all the strings that begin with 'x' first.
e.g. ['mix', 'xyz', 'apple', 'xanadu', 'aardvark'] yields
['xanadu', 'xyz', 'aardvark', 'apple', 'mix']
End of explanation
def sort_last(tuples):
    # +++your code here+++
    return
test(sort_last([(1, 3), (3, 2), (2, 1)]),
   [(2, 1), (3, 2), (1, 3)])
test(sort_last([(2, 3), (1, 2), (3, 1)]),
   [(3, 1), (1, 2), (2, 3)])
test(sort_last([(1, 7), (1, 3), (3, 4, 5), (2, 2)]),
   [(2, 2), (1, 3), (3, 4, 5), (1, 7)])
Explanation: B. sort_last
Given a list of non-empty tuples, return a list sorted in increasing
order by the last element in each tuple.
e.g. [(1, 7), (1, 3), (3, 4, 5), (2, 2)] yields
[(2, 2), (1, 3), (3, 4, 5), (1, 7)]
End of explanation
def linear_merge(list1, list2):
    # +++your code here+++
    return
test(linear_merge(['aa', 'xx', 'zz'], ['bb', 'cc']),
   ['aa', 'bb', 'cc', 'xx', 'zz'])
test(linear_merge(['aa', 'xx'], ['bb', 'cc', 'zz']),
   ['aa', 'bb', 'cc', 'xx', 'zz'])
test(linear_merge(['aa', 'aa'], ['aa', 'bb', 'bb']),
   ['aa', 'aa', 'aa', 'bb', 'bb'])
Explanation: C. linear_merge
Given two lists sorted in increasing order, create and return a merged
list of all the elements in sorted order. You may modify the passed in lists.
Ideally, the solution should work in "linear" time, making a single
pass of both lists.
End of explanation
<END_TASK>