merging of two sorted halfs without extra memory!

Question

given an integer array of which first and second half are sorted. write a function to merge the two parts to create one single sorted array in place(do not use extra space). one approach is eg: // 1,3,6,8,-5,-2,3,8

int l = 0;
int u = size;
int mid = (l+u)/2;
int i;
for (i = 0; i < mid; i++) {
  for (j = mid; j < size; j++) {
    if (a[i] >= a[j]) {
      temp = a[j];
      for (i = mid-1; i >= 0; i--)
        a[i+1] = a[i];
      a[0] = temp;
    }
  }
}

but i think there must be some O(n) algo for this..

Answer 1

Indeed there are O(n) algorithms for merging in-place. They're usually quite complex though. For few ideas, please see the papers such as Huang, Langston (PDF) or Katajainen, Pasanen, Teuhola (PostScript). These are actually defined based on precise terms of what kind of extra memory is allowed, without cheating by using recursion stack and so on.

Answer 2

You can do this by walking the array once, from 0 to it's last element. You just need to think about what you need to compare or swap the "current" element against, and it becomes quite easy.

You'll have to keep a few extra variables around to track the current element, and the "other" element you need to compare it to.

Also, you might want to look into the major C code formatting styles. There is no style that makes everyone 100% happy, but there are plenty of styles that make everyone unhappy.

---- Edited ----

Ok, this is much more like a "brain teaser" problem than a serious computer science problem. The issue is that "extra memory" is very poorly defined, and so there's a tons of way you can achieve the outcome if you only remember that recursion is allowed in the programming language, and that a recursive call requires extra stack (which nobody is going to consider memory allocation as it required by the programming language implementation).

Basically, such a question is meant to see if you look at a problem and see a recursive solution.

#include <stdio.h>

void sort(int index, int start1, int end1, int start2, int end2, int* array) {
  if (index >= end2) {
    return;
  }
  int lower;
  if (array[start1] <= array[start2]) {
    lower = array[start1];
    sort(index+1, start1+1, end1, start2, end2, array);
  } else {
    lower = array[start2];
    sort(index+1, start1, end1, start2+1, end2, array);
  }
  array[index]=lower;
}

int main(int argc, char** argv) {
  int a[] = {1,3,6,8,-5,-2,3,8};
  sort(0, 0, 3, 4, 7, a);
  int i;
  for (i = 0; i <= 7; i++) {
    printf("%d, ", a[i]);
  }
  printf("\n");
  return 0;
}

Is it a cheat? You decide. However, the sort was done in-place, and the cached numbers were neatly tucked away in local space in the call the stack, where you cannot really allocate / de-allocate them.

Extra optimizations are possible, but they are improvements of the core idea: use recursion and the call stack to cache information.

Answer 3

The best answer I've found, assuming you can't use any auxiliary memory, is to heapsort the array, which is theta(n log n), somewhat faster than your current insertion sort scheme.

Answer 4

any of following

void Merge(int array[N])
{
for(int i=N/2;i<N;i++){
    int j=i;
    while(array[j]<array[j-1]&& j>=1){
        int temp=array[j];
        array[j]=array[j-1];
        array[j-1]=temp;
        j--;
    }
}
}

void Merge2(int array[N])
{
for(int i=N/2;i<N;i++){
   int key=array[i];
   int j=i-1;
   while(array[j]>key&& j>=0){
           array[j+1]=array[j];
           j--;
   }
   array[j+1]=key;
}
}

Answer 5

I was looking at this again and here is your O(n-1) and memory(n+1):

/**
 * Created by deian on 2016-12-22.
 */
public class Merge {
    public static void swap(int[] a, int i1, int i2) {
        int t = a[i1];
        a[i1] = a[i2];
        a[i2] = t;
    }

    public static void merge(int[] a) {
        int i1 = 0;
        int i2 = a.length / 2;

        System.out.printf("    %s,      i(%d,%d)       \n",    Arrays.toString(a),    i1, i2   );
        for (int di = 0; di < a.length-1; di++) {
            int ni;
            int oi1=i1;
            int oi2=i2;
            // i1 and i2 - always point to the smallest known numbers
            if (a[i1] > a[i2]) {
                ni = i2;
                i2++;
                if (i2>=a.length) {
                    i2--;
                }
            } else {
                ni = i1;
                i1++;
                if (i1 >= i2) {
                    i1 = di;
                }
            }
            if (di == i1) {
                i1 = ni;
            }
            swap(a, di, ni);
            System.out.printf("#%d: %s, i(%d,%d)s(%d>%d)i(%d,%d) \n", di+1, Arrays.toString(a), oi1, oi2,ni, di, i1,i2);
        }
        System.out.printf("    %s\n", Arrays.toString(a));
    }

    public static void main(String[] args) {
//        int[] a = new int[]{1, 3, 6, 8, -5, -2, 3, 8};
//        int[] a = new int[]{1, 3, 6, 8, -5, 2, 3, 8};
        int[] a = new int[]{1, 5, 6, 8, -5, 2, 3, 4};
        merge(a);
    }
}