Sort An Increasing-Decreasing Array

Problem

An array's elements repeatedly increase up to a certain index after which they decrease to a small value, then again increase. This repeated k times.
for example, given array {1, 2, 3, 1, 2, 4, 5, 1, 3, 4}, the output should be
{1, 1, 1, 2, 2, 3, 3, 4, 4, 5}

Solution

Fasted sort uses time cost NlogN to sort the array. However, this array is partially sorted. We can use N step to find all the boundaries or the increasing sub-arrays, then we can use priority queue to decide which subarray should provide the next element. The time cost is O(N + N*klogk) which is dominant by O(Nklogk), when k is small, klogk is smaller than logN. The space cost is O(N), we need to create a new array, it is not in place sort.

import java.util.*;
public class KInDeArrays {
  //123 1245 134
  //           .
  //0 - [0, 2, 0, 0], 1 - [3, 6, 3, 1], 2 - [7, 9, 7, 2],
  //false
  public static Map<Integer, int[]> findBoundary(int[] a) {
    Map<Integer, int[]> kArrays = new HashMap<>();
    int k = 0;
    boolean isStart = true;
    for(int i = 0; i < a.length; i++) {
      if(i == 0 || a[i-1] > a[i]) {
          isStart = true;
      }
      if(isStart) {
        int[] arr = kArrays.get(k);  //1
        if(arr == null) {
          kArrays.put(k, new int[]{i, i, i});
          isStart = false;
        } else {
          arr[1] = i - 1;
          kArrays.put(++k, new int[]{i, i, i});
          isStart = false;
        }
      }
    }
    int[] arr = kArrays.get(k);
    arr[1] = a.length - 1;
    return kArrays;
  }
  //0 - [0, 2, 0], 1 - [3, 6, 3], 2 - [7, 9, 7],
  //
  public static int[] sort(int[] a, Map<Integer, int[]> boundaries) {
    Queue<int[]> pq = new PriorityQueue<>(boundaries.size(), (i, j) -> a[i[2]] - a[j[2]]);
    for(int[] arr : boundaries.values()) {
      pq.add(arr);   //    [7, 9, 7] [0, 2, 2]  [3, 6, 4]
    }
    int r = 0;//{1, 2, 3,  1, 2, 4, 5,  1, 3, 4}
    int[] result = new int[a.length]; //[1,...2, ]
    while(!pq.isEmpty()) {
      int[] arr = pq.poll();
      result[r++] = a[arr[2]]; //1
      int curIndex = arr[2];
      if(curIndex < arr[1]) {
        arr[2] = curIndex + 1;
        pq.add(arr);
      }
    }
    return result;
  }
 
  public static void main(String...args) {
    int[] a = {1, 2, 3, 1, 2, 4, 5, 1, 3, 4};
    int[] result = sort(a, findBoundary(a));
    Arrays.stream(result).forEach(i -> System.out.print(" " + i));
  }
}

Time cost O(Nklogk), space cost O(N).