std::stable_sort vs std::sort

https://leetcode.com/problems/largest-number/

When I was solving the above problem, I came across the case where std::sort() was giving me a runtime error, but replacing it with std::stable_sort() then there was no runtime error. Why?

Line is highlighted with the arrow sign on right

Code:

class Solution {
public:
    string reverse(string str)
    {
        int n=str.length();
        for(int i=0;i<n/2;i++)
        {
            swap(str[i],str[n-i-1]);
        }
        return str;
    }

    static bool comp(string s1,string s2)
    {
        int min_val=min(s1.length(),s2.length());
        int i=0;
        bool flag=false;
        for(;i<min_val;i++)
        {
            if((s1[i]-'0')==(s2[i]-'0'))
            {
                flag=true;
                continue;
            }

            return (s1[i]-'0')>(s2[i]-'0');
        }

        if(flag==true && s1.length()==s2.length())
        {
            return s1==s2;
        }

        string s1_temp=s1;
        string s2_temp=s2;
        s1_temp+=s2;
        s2_temp+=s1;

        return s1_temp>s2_temp;
    }

    string largestNumber(vector<int>& nums)
    {
        string str="";
        vector<string> inp;

        for(int i=0;i<nums.size();i++)
        {
            string temp="";
            long long int num=nums[i];
            if(num!=0)
            {
                while(num!=0)
                {
                    temp+=((num%10)+'0');
                    num/=10;
                }
            }
            else
            {
                temp+=(num+'0');
            }

            inp.push_back(reverse(temp));
        }

        stable_sort(inp.begin(),inp.end(),comp); // <-- This Line

        string res="";

        for(int i=0;i<inp.size();i++)
        {
            res+=inp[i];
        }
        cout<<"yes"<<endl;
        if(res[0]=='0')
        {
            return "0";
        }

        return res;
    }
};

TestCase:

[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]

Can anybody give me the reason why this happened?

This is actually a very interesting bug! I have not tested whether this is a leetcode specific issue, but running this code with sort() on leetcode, we get the following error:

Line 431: Char 55: runtime error: pointer index expression with base 0xbebebebebebebebe overflowed to 0x7d7d7d7d7d7d7d7c (basic_string.h)
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /usr/bin/../lib/gcc/x86_64-linux-gnu/8/../../../../include/c++/8/bits/basic_string.h:440:55

which seems to suggest that we're running out of memory for some reason. The fact that this code works with stable_sort() but not sort() suggests that this might have something to do with the fact that "stable_sort preserves the relative order of the elements with equivalent values" (http://www.cplusplus.com/reference/algorithm/stable_sort/).

The line of code where this is relevant is here

if(flag==true && s1.length()==s2.length())
{
    return s1==s2;
}

And indeed if we change this to

if(flag==true && s1.length()==s2.length())
{
    return s1!=s2;
}

which doesn't affect the results, because if, at this point, flag == true and both strings have the same length, then they are both equivalent, and swapping string positions does not affect the outcome.

BUT we bypass the error. @Vikram Keswani I hope this solves your issue. Personally I would also just replace the code in the comp() function with return s1 > s2; which should provide the same behaviour as the code that you have.

p.s. I shall leave the pieces of the puzzle here, but if someone more experienced (or when I find more time) would like to investigate this mysterious memory issue further, that'd be great.

Incidentally, the minimum length input required to reproduce this error on leetcode is [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] which is 17 0's (a strange number).