Twist Sort: A Merge-Based Sorting Challenge

Given a list of n integers, your task is to sort the array using the Twist Sort algorithm. The algorithm works by first sorting each adjacent pair of elements and then iteratively merging these sorted pairs until the entire list is sorted. Formally, for an array \(A = [a_1, a_2, \ldots, a_n]\), the process is defined as follows:

1. Divide the array into segments of two elements (if \(n\) is odd, the last segment contains a single element). For each segment, if the two elements are out of order, swap them so that the segment is sorted.

2. Iteratively merge adjacent segments using the standard merge procedure (as in merge sort) to produce longer sorted segments.

The final output is the entire sorted array in ascending order.

Input Constraints: \(1 \le n \le 10^5\). The integers can be negative and may be large in absolute value.

inputFormat

The input is read from standard input. It consists of two lines:

• The first line contains a single integer \(n\) representing the number of elements.
• The second line contains \(n\) space-separated integers.

outputFormat

Print the sorted array in ascending order on a single line. The integers should be separated by a space.

6
4 3 2 8 1 5

1 2 3 4 5 8