1
$\begingroup$

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.

$\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 Ko
    Dec 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$
    – kelalaka
    Dec 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

1 Answer 1

2
$\begingroup$

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.
$\endgroup$
2
  • $\begingroup$ Note that $k$ means something different in the question. $\endgroup$
    – Raphael
    Dec 27, 2018 at 9:53
  • $\begingroup$ In practice, $k$ can be huge (think Unicode) so be careful with that. $\endgroup$
    – Raphael
    Dec 27, 2018 at 9:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.