Sort an Increasing-Decreasing Array

EPI 11.2

Description:

array先increase，然后decrease，然后再increase，不断交替，但是每一段长度不定。

Example:

Note

Idea:

切段，每一段放入一个increase的array，形成vector<vector<int>>,然后合并sorted array。

time: o(nlogk), k is averaged length of each segment

Code:

Code