Description
Credit: KKOMDASTRO
Nangong Yu's business is booming. Tickets for her idol group's next concert were over the moon. But she has a problem sorting the ticket, and she would like you to help her.
Nangong's given you a template code with the input and output already handled. Complete the two functions merge(left, right) and merge_sort(arr). merge_sort should return a new sorted list.
Do NOT modify the code under #---- Do not modify below ---- or use Python's built-in sorting functions, otherwise Nangong won't accept your solution and will fire you.
To help you further, Nangong also gave you this link: https://www.geeksforgeeks.org/dsa/merge-sort/
Template code
def merge(left, right):
"""Merge two sorted lists into one sorted list and return it."""
# TODO: implement this function, you can delete the pass command.
pass
def merge_sort(arr):
"""Sort arr using merge sort and return a new sorted list."""
# TODO: implement this function, you can delete the pass command.
pass
# ---- Do not modify below ----
def main():
n = int(input())
data = input().split()
arr = list(map(int, data[0:n]))
result = merge_sort(arr)
print(" ".join(map(str, result)))
if __name__ == "__main__":
main()
Input
- The first line contains an integer $n$ ($1 \le n \le 100000$).
- The second line contains n integers $a_1$, $a_2$, $...$, $a_n$ ($-10^9 \le a_i \le 10^9$), separated by spaces.
Output
Print the sorted sequence on one line, in ascending order, separated by single spaces.