<p>Given an array of strings <code>strs</code>, group the <span data-keyword="anagram">anagrams</span> together. You can return the answer in <strong>any order</strong>.</p>

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

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">strs = [&quot;eat&quot;,&quot;tea&quot;,&quot;tan&quot;,&quot;ate&quot;,&quot;nat&quot;,&quot;bat&quot;]</span></p>

<p><strong>Output:</strong> <span class="example-io">[[&quot;bat&quot;],[&quot;nat&quot;,&quot;tan&quot;],[&quot;ate&quot;,&quot;eat&quot;,&quot;tea&quot;]]</span></p>

<p><strong>Explanation:</strong></p>

<ul>
	<li>There is no string in strs that can be rearranged to form <code>&quot;bat&quot;</code>.</li>
	<li>The strings <code>&quot;nat&quot;</code> and <code>&quot;tan&quot;</code> are anagrams as they can be rearranged to form each other.</li>
	<li>The strings <code>&quot;ate&quot;</code>, <code>&quot;eat&quot;</code>, and <code>&quot;tea&quot;</code> are anagrams as they can be rearranged to form each other.</li>
</ul>
</div>

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

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">strs = [&quot;&quot;]</span></p>

<p><strong>Output:</strong> <span class="example-io">[[&quot;&quot;]]</span></p>
</div>

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

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">strs = [&quot;a&quot;]</span></p>

<p><strong>Output:</strong> <span class="example-io">[[&quot;a&quot;]]</span></p>
</div>

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

<ul>
	<li><code>1 &lt;= strs.length &lt;= 10<sup>4</sup></code></li>
	<li><code>0 &lt;= strs[i].length &lt;= 100</code></li>
	<li><code>strs[i]</code> consists of lowercase English letters.</li>
</ul>

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) 
    {
        std::vector<std::string> s = strs;
        std::vector<std::vector<std::string>> v;
        //std::vector<std::unordered_map<int, int>> um;

        std::unordered_map<std::string, std::vector<std::string>> um;
        

        for(int i = 0; i < s.size(); i++)
        {
            //std::string ss = s[i];
            std::sort(s[i].begin(), s[i].end());
            um[s[i]].push_back(strs[i]);
            // m[s[i]].push_back(strs[i]);
            //std::vector<int> n;
        }

        for(auto i : um)
        {
            v.push_back(i.second);
        }

        return v;
        
    }

    void mergeSort(std::string& s)
    {
        for(int ms = 1; ms < s.length(); ms = ms * 2)
        {
            for(int ls = 0; ls + ms - 1 < s.length() - 1; ls += (ms * 2))
            {
                int mid = min(ls + ms - 1, s.length() - 1);
                int re = min(ls + (ms * 2) - 1, s.length() - 1);

                merge(s, ls, mid, re);
            }
        }
    }
    void merge(std::string& s, int ls, int mid, int re)
    {

        int las = mid - ls + 1;
        int ras = re - mid;

        int la[las];
        int ra[ras];

        int li;
        int ri;
        int si = ls;

        for(li = 0; li < las; li++)
        {
            la[li] = s[si];
            si++;
        }

        for(ri = 0; ri < ras; ri++)
        {
            ra[ri] = s[si];
            si++;
        }

        li = 0;
        ri = 0;
        si = ls;

        while (li < las && ri < ras)
        {
            if (la[li] < ra[ri])
            {s[si] = la[li]; li++;}
            else {s[si] = ra[ri]; ri++;}
            si++;
        }

        while (li < las)
        {
            s[si] = la[li];
            li++;
            si++;
        }

        while (ri < ras)
        {
            s[si] = ra[ri];
            ri++;
            si++;
        }

    }
    int min(int x, int y)
    {return (x < y)? x : y;}        
    
};
25834