Given $k$ arbitrary words, such as $\{\text{"fjqke"}, \text{"gbqig"}, \text{"a"}\}$, is there a way to mergesort these words in linear time so that the final output would be "abefgggijkq"? I tried to approach it by first sorting all the words independently and then merging the words into the final output, but sorting all the words takes $O(kn\log n)$ time.
$\begingroup$
$\endgroup$
5
-
$\begingroup$ Yes, if we assume the alphabet is fixed and finite, which is a reasonable and common assumption. Would you prefer an answer along this assumption? $\endgroup$– John L.Dec 25, 2018 at 16:55
-
$\begingroup$ @Apass.Jack Yes I'd love an answer with those assumptions! $\endgroup$– Brian KoDec 27, 2018 at 6:10
-
$\begingroup$ @kelalaka, can you update your answer with the linear time algorithm under that assumption? $\endgroup$– John L.Dec 27, 2018 at 6:41
-
1$\begingroup$ Updated with the finite case. $\endgroup$– kelalakaDec 27, 2018 at 9:39
-
1$\begingroup$ Note that the $O(k \cdot n \log n)$ bound is rather pessimistic. Expressing the runtime nicely in term of input size $n$ is a little fiddlesome, but the upper bound $O(k \cdot N \log N)$ with $N = \max \{n_i \mid 1 \leq i \leq k\}$ the largest word length is more informative already: if your words are roughly equal in length, you get $O(n \log n)$ sorting cost in total! (Merging comes on top.) Also, for long words, you can trivially parallelize the algorithm (in practice). In summary, I think the algorithm you reject is not as bad as you think, and probably quite good. And it's simple. $\endgroup$– Raphael ♦Dec 27, 2018 at 9:59
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
General case:
If there is a linear time sorting algorithm $\mathcal{A}$ for this problem, then one can divide a list into random parts, and use $\mathcal{A}$ to sort. But comparison based sorting has a lower bound $\Omega(n \log n)$. Therefore there is no such algorithm $\mathcal{A}$.
Note: Merge routine combines sorted arrays into one sorted array. There is a similar problem to your problem called k-way merging, but that is also required sorted arrays. The complexity of k-way is $\mathcal{O}(n \log k)$
Finite alphabet case:
If we assume that the alphabet is finite, and in your case it seems only lower case letters then one can use the Counting Sort algorithm.
Assuming that the total length of the words is $n$ and there are at most $t=26$ letters, the Counting sort can sort this array in $\mathcal{O}(n+t)$-time.
To achieve this with Counting sort, you need to convert this into an array and map the letters with an integer. And, call;
countingSort(array,26)
The Counting sort is not in-place. The space requirement for this question is $\mathcal{O}(t)$
- Note 1: Counting sort is not a comparison based sorting algorithm, it uses counting, thus it is not bounded by the lower bound of the comparison based sorting algorithms.
- Note 2: Counting sort, also, can be implemented stable.
