Let S1,S2..Sk be k different sequences whose elements have integer
keys in the range [0,N-1], for some parameter N >=2. Describe an
algorithm running in O(n+N) time for sorting all the sequences (not as
a union), where n denotes the total size of all the sequences

Thank you for your question.  
 
However, I believe that to answer it well, your question will require
more time and effort than the average amount of time and effort
associated with this price. Here is a link to guidelines about pricing
your question, in the pricing guide:
https://answers.google.com/answers/pricing.html

You can not sort in less the O(n*log(n)),if you assume that the input is Random

It seems possible.
The range of the element is given, we can use special method.
Here is my code:

// k is the array [0..n-1] with integer element [0..N-1]
void sort(int k[], int N, int n)
{
	int i, j, p, *map;
	
	// alloc a temporory array map[0..N-1] and set it all 0.
	map = (int *)malloc(N * sizeof(int));
	memset(map, 0, sizeof(int) * N);
	
	for(i = 0;i < n;i ++)
	{
		map[k[i]]++;
	}
	p = 0;
	for(i = 0;i < N;i++)
	{
		for(j = 0;j < map[i];j++)
		{
			k[p++] = i;
		}
	}
	free(map);
}

Sorting a single sequence with 0,N-1 keys is relatively easy. Since
the key range is given you can use a radix sort or something similar (this works
because the keys are integers!)

By representing an integer in binary you need a fixed number of passes
(lg(N)) over the sequence in order to sort it. In each pass, i.e the
Ith pass, you simply exchange the items whose Ith bit is 1 with those
whose Ith bit is 0. By going
from low bits (I=0) to high bits (I=ceil(lg(N))) you get a guaranteed
correct sort. You can then apply this for every sequence.

An alternative solution implies the use of a sorting "network", i.e. a
fixed way of sorting N-tuples. This is a theoretical construct, but
since N is known beforehand it could work for each sequence once
"built" (imagine a specialized N-tuple sorting machine). I've never
written anything like that, mostly useful in theory.

This is a very rough outline. I wouldn't answer this question for
$2.00 but I did happen to have some free time.

PKT