Thank you for this reply,

I spent like half an hour debugging with custom inputs only to find out I missed the part where you needed to swap at every depth multiple of k.

After that, my first algorithm was indeed correct :)