Trouble Sort

Design a hardware module for the Trouble Sort problem.

Given an array v, Trouble Sort conceptually splits the elements at even indices and odd indices, sorts each group independently, and then interleaves them back together.

Your task is to report whether the final interleaved array is sorted.

• output 0 if the Trouble Sort result is fully sorted
• otherwise output the first index i such that result[i] < result[i - 1]

Hardware I/O Encoding

• v is a one-dimensional input stream of unsigned 16-bit integers
• the stream length is at most 50
• the output is one unsigned 16-bit integer
• the output is either 0 or the first bad index after Trouble Sort finishes

Examples

Example 1

• input v = [5, 6, 8, 4, 3]
• output: 0

Even-indexed elements are [5, 8, 3], odd-indexed elements are [6, 4], and Trouble Sort rebuilds [3, 4, 5, 6, 8], which is sorted.

Example 2

• input v = [8, 9, 7]
• output: 2

Trouble Sort rebuilds [7, 9, 8]. The first out-of-order position is index 2 because 8 < 9.

Example 3

• input v = [1, 2, 3, 4, 5]
• output: 0

The reconstructed array stays sorted.

Source: Google Code Jam 2018 Qualification Round - Trouble Sort