396. Sort List in O(n log n) Time and O(1) Space

Given the head of a linked list, sort it in ascending order in O(n log n) time using O(1) auxiliary space (bottom-up merge sort). The list is given as an array; return the sorted array.

Input: An array of node values.

Output: Array — the sorted list.

Examples

Input: [4,2,1,3]
Output: [1,2,3,4]
Explanation: Sorted ascending.

Input: [-1,5,3,4,0]
Output: [-1,0,3,4,5]
Explanation: Includes negatives.

Input: []
Output: []
Explanation: Empty.

Constraints

• 0<=n<=5*10^4
• -10^5<=value<=10^5

Asked by