The Full Counting Sort

Use the counting sort to order a list of strings associated with integers. If two strings are associated with the same integer, they must be printed in their original order, i.e. your sorting algorithm should be stable. There is one other twist: strings in the first half of the array are to be replaced with the character - (dash, ASCII 45 decimal).

Insertion Sort and the simple version of Quicksort are stable, but the faster in-place version of Quicksort is not since it scrambles around elements while sorting.

Design your counting sort to be stable.

Example:

Input:  n=6,  arr={{"0","ab"},{"6","cd"},{"0","ef"},{"6","gh"},{"4","ij"},{"0","ab"}}
Output: - - ab ij - gh 

Approach

C++

#include <bits/stdc++.h>
using namespace std;

bool cmp(pair<int, pair<int, string>> a, 
    pair<int, pair<int, string>> b)
{
    if (a.first == b.first)
    {
        return a.second.first < b.second.first;
    }
    return a.first < b.first;
}

void countSort(vector<vector<string>> arr)
{

    int n = arr.size();
    int mid = n / 2;
    vector<pair<int, pair<int, string>>> res;
    for (int i = 0; i < arr.size(); i++)
    {
        string x = arr[i][0];
        string y = arr[i][1];
        if (i < mid)
        {
            res.push_back({stoi(x), {i, "-"}});
        }
        else
            res.push_back({stoi(x), {i, y}});
    }
    sort(res.begin(), res.end(), cmp);
    for (int i = 0; i < res.size(); i++)
    {

        cout << res[i].second.second << " ";
    }
}

int main()
{
    int n = 6;

    vector<vector<string>> arr = {{"0", "ab"}, {"6", "cd"}, {"0", "ef"}, 
                                {"6", "gh"}, {"4", "ij"}, {"0", "ab"}};
    countSort(arr);

    return 0;
}