CareerCup

keep a heap. add elements to the heap until it reaches k elements. when this happens, keep adding elements, but for every element added, remove the min from the heap and output it. when there are no more elements, remove and output all the heap elements.

Use insertion sort. It will run in O(N x K). But since K is constant, it should run in O(N).

I had another algorithm with O(1) space and O(n * Log k) time complexity.

1. Start with a window of min(2k, items in array). Sort it.
2. First k elements are sorted
3. Move window min(k, items left in array) index ahead
4. Goto step1 till items remaining in the array

sorting 2k Elements O(2k log 2k), n/k times
O(2k * n/k log 2k) = O(2n * log 2k) = O(n log k)

public static void order(int a[], int k) {
        for (int i = 1; i < a.length-1; i++) {
            if (a[i] > a[i + 1]) {
                swap(a, i, i+k);
            } else if (a[i - 1] > a[i]) {
                swap(a, i, i-k);
            }
        }
    }

    private static void swap(int a[], int i, int k) {
        int tmp = a[i];
        a[i] = a[k];
        a[k] = tmp;

}

public static void order(int a[], int k) {
        for (int i = 1; i < a.length-1; i++) {
            if (a[i] > a[i + 1]) {
                swap(a, i, i+k);
            } else if (a[i - 1] > a[i]) {
                swap(a, i, i-k);
            }
        }
    }

    private static void swap(int a[], int i, int k) {
        int tmp = a[i];
        a[i] = a[k];
        a[k] = tmp;

}

The optimal single threaded solution can be described something like this
implement a routine, which given l element between i,i+l indexes of an array, sort this l size subarray using inplace l x log(l) time algorithm.(options are : heap sort, or quick sort with proper pivot).
Once we have this routine, we can call it n/k times to sort the whole array as explained by @pc.
I am presenting the multithreaded algorithm which can solve this problem in n/r x log(k) time with r as maximum threads systme can allocate to this program.

A <- input array, k is the condition as per this question
Step : 1
do Parallel for j = 0; j < n; j  = j + 3k
sort(A, j, j+3k-1)

Step  : 2
do parallel for j = 2; j < n; j = j + 3k;
sort (A, j, j + 2k -1)

I havn't considered the edge cases in both the steps for simplicity, and btw they can only add upto O(k x log(k)) more complexity to the total complaxity.
one can easily check that given r threads, both the steps will only take O(n/r x log(k)) time.

void sort(int A[], int n, int k)
	{
		assert(A != NULL && n > 0 && k > 0 && k <= n);

		priority_queue<int> que;

		for (int i = 0; i < k; ++i) que.push(A[i]);

		for (int i = 0; i < n - k; ++i)
		{
			a[i] = que.top(); que.pop(); que.push(a[i + k]);
		}

		for (int i = n - k; i < n; ++i)
		{
			a[i] = que.top(); que.pop();
		}
	}

Why not bubble sort? Typically, bubble sort is n^2 because for each number, there may be up to n swaps needed. But in this case, for any number, there are at most k swaps needed, so the complexity for bubble sort in this case should be o(kn), or o(n), since k is constant.

Use insertion sort. It will run in O(N x K). But since K is constant, it should run in O(N).

Use insertion sort. It will run in O(N x K). But since K is constant, it should run in O(N).

Use insertion sort. It will run in O(N x K). But since K is constant, it should run in O(N).

Use insertion sort. It will run in O(N x K). But since K is constant, it should run in O(N).