<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:
    # mlogm, where m is the number of different word sizes
    # m will be n in worst case, where n is the number of words
    def arrangeWords(self, text: str) -> str:
        a = text.split(" ")

        groups = {}
        for i, word in enumerate(a):
            if len(word) in groups:
                groups[len(word)].append(i)
            else:
                groups[len(word)] = [i]

        keys = list(groups.keys())
        self.quick_sort(keys, 0, len(groups.keys()) - 1)

        merged_arr = []
        for key in keys:
            merged_arr.append(groups[key])
        
        merged_arr = self.flatten(merged_arr)
        
        res = ""
        for i in merged_arr:
            res += a[i]+" "
        
        res = res.lower()[:-1]
        res = res[0].upper()+res[1:]
        return res



    def flatten(self, mda):
        res = []
        for arr in mda:
            for i in arr:
                res.append(i)
        return res

    def partition(self, arr, low, high):
  
        # Choose the pivot
        pivot = arr[high]
        
        i = low - 1
        
        # Traverse arr[low..high] and move all smaller
        # elements on the left side. Elements from low to 
        # i are smaller after every iteration
        for j in range(low, high):
            if arr[j] < pivot:
                i += 1
                arr[i], arr[j] = arr[j], arr[i]
        
        # Move pivot after smaller elements and
        # return its position
        arr[i + 1], arr[high] = arr[high], arr[i + 1]
        return i + 1

    # The QuickSort function implementation
    def quick_sort(self, arr, low, high):
        if low < high:
            # pi is the partition return index of pivot
            pi = self.partition(arr, low, high)

            # Recursion calls for smaller elements
            # and greater or equals elements
            self.quick_sort(arr, low, pi - 1)
            self.quick_sort(arr, pi + 1, high)

19200