DSA interview question

Sort a K-Sorted (Nearly Sorted) Array

Easy · Data structures · Topics: heap, merge sort

The problem

A log collector receives events that are almost in timestamp order: network jitter can delay an event, but never by more than k positions from where it belongs. A general sort costs O(n log n). Knowing the disorder is bounded by k, a min-heap of k + 1 elements is enough. The smallest remaining element must be among the next k + 1 candidates, so repeatedly pop the minimum into the output and push the next element. That's O(n log k).

Example: [6, 5, 3, 2, 8, 10, 9], k = 3 → [2, 3, 5, 6, 8, 9, 10].

Function signature

vector<int> sortKSorted(const vector<int>& arr, int k);  // every element is within k positions of its sorted place

Test cases

Input `(arr, k)`	Output	Explanation
`([6, 5, 3, 2, 8, 10, 9], 3)`	`[2, 3, 5, 6, 8, 9, 10]`
`([10, 9, 8, 7, 4, 70, 60, 50], 4)`	`[4, 7, 8, 9, 10, 50, 60, 70]`
`([1, 2, 3], 0)`	`[1, 2, 3]`	Already sorted
`([2, 1], 1)`	`[1, 2]`
`([3, 1, 2], 2)`	`[1, 2, 3]`

(Confirm: the input is guaranteed k-sorted; output in ascending order.)

How interviewers phrase it

"Given an array where each element is at most k away from its target position, sort it efficiently" (GeeksforGeeks "Nearly sorted").

Clarifying questions to ask

Is k guaranteed? (Yes: every element is within k of its sorted position.)
In place or a new array?
How large are n and k? (k is much smaller than n makes the heap worthwhile.)

Follow-ups to expect

"Why k + 1 elements in the heap?"
"Why is it O(n log k)?"
"Would insertion sort work?"
"Can it be done in place?"
"What happens if the input isn't really k-sorted?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview