Sort numbers in an array without changing even numbers position using Java-8

I really liked the idea of using a sorted Stack, but it is not easily parallelizable and got me curious how to solve that.

My idea is sorting indices of uneven elements and depending on the position of the index we can distinguish during the creation of the result array if a number is even or not.

public int[] sortUnevenElements(int[] nonSorted) {
    int[] unevenIndices = IntStream.range(0, nonSorted.length).filter(i -> nonSorted[i] % 2 != 0).toArray();
    int[] sortedUnevenIndices = Arrays.stream(unevenIndices, 0, unevenIndices.length).boxed()
          .sorted(Comparator.comparingInt(i -> nonSorted[i])).mapToInt(Integer::intValue).toArray();
    return IntStream.range(0, nonSorted.length).map(i -> {
        int idx = Arrays.binarySearch(unevenIndices, i);
        return idx >= 0 ? nonSorted[sortedUnevenIndices[idx]] : nonSorted[i];
    }).toArray();
}

One can think of a solution like: First we extract the odd integers from the nonSorted[] and put them on a stack in sorted fashion.

Why we should use the stack in a sorted fashion??

The final array needs to be sorted on odd Integers basis, the stack follows FIFO(First in Last Out) policy.

Now we take an Instream and run it from 0 to nonSorted.length-1 and check the original nonSorted for the odd Integer; as soon as we find one we replace it with the first element of the stack and pop() the element from the stack.

Note: One needs to play around the stack as not every time you will need sorted elements in the stack, but in OP's case this happens to be.

int[] nonSorted = new int[]{3, 4, 5, 2, 1, 6, 9, 8, 7, 0};

LinkedList<Integer> stack = Arrays.stream(nonSorted)
            .sorted().filter(s -> s % 2 != 0).boxed()
            .collect(Collectors.toCollection(LinkedList::new));

int[] expected = IntStream.rangeClosed(0, nonSorted.length - 1)
       .map(s -> nonSorted[s] % 2 != 0 ? stack.pop():nonSorted[s]) 
       .toArray();