Merge Sort on Singly Linked List

Your task is to implement an efficient merge sort algorithm on a singly linked list. Given a linked list containing \(N\) integers, sort the linked list in ascending order using the merge sort algorithm. Merge sort works by dividing the list into two halves, recursively sorting each half, and then merging the two sorted halves together. The expected time complexity is \(O(n \log n)\). This problem tests your understanding of linked list manipulation as well as divide and conquer algorithms.

inputFormat

The input consists of two lines. The first line contains an integer (N), the number of nodes in the linked list. The second line contains (N) space-separated integers representing the node values. If (N = 0), the second line will be omitted.

outputFormat

Output the sorted linked list node values in a single line, separated by a space. If the linked list is empty, output nothing.## sample

4
4 2 1 3

1 2 3 4