Better way to sort a stack / algorithm improvement + space & time reasoning

You're reinventing the Counting sort algorithm, which runs in linear time O(n).

Instead of a HashMap you can use a plain array. And you definitely don't need this swarm of redundant while-loops.

Here's the description of the algorithm in pseudocode:

function CountingSort(input, k)

count ← array of k + 1 zeros
output ← array of same length as input

for i = 0 to length(input) - 1 do      // STEP 1
    j = key(input[i])
    count[j] = count[j] + 1

for i = 1 to k do                      // we don't need this step
    count[i] = count[i] + count[i - 1]

for i = length(input) - 1 down to 0 do // STEP 2
    j = key(input[i])
    count[j] = count[j] - 1
    output[count[j]] = input[i]

return output

For your use-case you don't need the second for-loop where there the cumulative frequency is being calculated.

So to address the problem, we need to take the following step:

• STEP 1 is to generate a histogram of frequencies.

• STEP 2 is to iterate over frequencies backwards (i.e. starting from the very last index of the array) and push the values equal to index + minValue (in this case 1). Each value should be pushed the number of times equal to its frequency.

Here's an implementation:

final int min = 1;
final int max = 4;

int[] freq = new int[max - min + 1]; // histogram, i.e. array of frequencies of values in range [min, max]
        
// STEP 1: generating a histogram

while (!stack.isEmpty()) {
    int next = stack.pop();
    if (next >= min && next <= max) freq[next - min]++; // calculating the frequency of each element
}
    
// STEP 2: populating the stack in sorted order
        
for (int i = freq.length - 1; i >= 0; i--) {
    while (freq[i] > 0) {
        stack.push(i + min);
        freq[i]--;
    }
}

return stack;

If you want to use the HashMap, fine, you can apply the same algorithm, just don't create redundant loops.

Regarding the time complexity in both cases it would be linear as I've said before. Array would perform slightly better, but more importantly it gives you a better feeling of the internal mechanics of the algorithm.

final int min = 1;
final int max = 4;
        
Map<Integer, Integer> freq = new HashMap<>(); // histogram, i.e. array of frequencies of values in range [min, max]

// STEP 1: generating a histogram
        
while (!stack.isEmpty()) {
    int next = stack.pop();
    if (next >= min && next <= max) 
        freq.merge(next, 1, Integer::sum); // calculating the frequency of each element
}
    
// STEP 2: populating the stack in sorted order
    
for (int i = max; i >= min; i--) {
    int count = freq.get(i);
    while (count > 0) {
        stack.push(i + min);
        count--;
    }
}
        
return stack;

Sidenote: class java.util.Stack is legacy and not encouraged to be used. When you need an implementation of Stack data structure in Java, use classes that implement Deque interface.