<p>Given a sentence&nbsp;<code>text</code> (A&nbsp;<em>sentence</em>&nbsp;is a string of space-separated words) in the following format:</p>

<ul>
	<li>First letter is in upper case.</li>
	<li>Each word in <code>text</code> are separated by a single space.</li>
</ul>

<p>Your task is to rearrange the words in text such that&nbsp;all words are rearranged in an increasing order of their lengths. If two words have the same length, arrange them in their original order.</p>

<p>Return the new text&nbsp;following the format shown above.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> text = &quot;Leetcode is cool&quot;
<strong>Output:</strong> &quot;Is cool leetcode&quot;
<strong>Explanation: </strong>There are 3 words, &quot;Leetcode&quot; of length 8, &quot;is&quot; of length 2 and &quot;cool&quot; of length 4.
Output is ordered by length and the new first word starts with capital letter.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> text = &quot;Keep calm and code on&quot;
<strong>Output:</strong> &quot;On and keep calm code&quot;
<strong>Explanation: </strong>Output is ordered as follows:
&quot;On&quot; 2 letters.
&quot;and&quot; 3 letters.
&quot;keep&quot; 4 letters in case of tie order by position in original text.
&quot;calm&quot; 4 letters.
&quot;code&quot; 4 letters.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> text = &quot;To be or not to be&quot;
<strong>Output:</strong> &quot;To be or to be not&quot;
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>text</code> begins with a capital letter and then contains lowercase letters and single space between words.</li>
	<li><code>1 &lt;= text.length &lt;= 10^5</code></li>
</ul>

class Solution {
    void mergesort(vector<string> *v)
    {
        vector<string>::iterator p;
        string *q, *z;
        int i, j, k, left, m, n, rend, rght;

        n = v->size();
        z = new string[n];
        p = v->begin();
        q = &z[0];
        for (k = 1; k < n; k *= 2)
            for (left = 0; left + k < n; left += k * 2) {
                rght = left + k;        
                rend = std::min(rght + k, n);
                m = i = left;
                j = rght; 
                while (i < rght && j < rend) { 
                    z[m] = ((*v)[i].length() <= (*v)[j].length()) ? (*v)[i++] : (*v)[j++];
                    m++;
                }
                std::copy(p + i, p + rght, &z[m]);
                std::copy(p + j, p + rend, &z[m + rght - i]);
                std::copy(&z[left], &z[rend], p + left);
            }
        delete[] z;
    }

public:
    string arrangeWords(string text)
    {
        vector<string> *w;
        string str;
        int i, j, l;
        
        w = new vector<string>();
        l = text.length();
        i = 0;
        do {
            j = text.find(' ', i);
            if (j == string::npos)
                j = l;
            if (j > i) {
                if (std::isupper(text[i])) {
                    str = "";
                    str.push_back(std::tolower(text[i]));
                    str += text.substr(i + 1, j - i - 1);
                } else
                    str = text.substr(i, j - i);
                w->push_back(str);
            }
            i = j + 1;
        } while (i < l);
        
        mergesort(w);
        str = "";
        str.push_back(std::toupper((*w)[0][0]));
        str += (*w)[0].substr(1);
        for (i = 1; i < w->size(); i++) {
            str.push_back(' ');
            str += (*w)[i];
        }

        return str;
    }
};
20700