I'm trying to solve 103 — Stacking Boxes on UVa online judge. My idea is first, sort all the box that no box can be nested in the previous box, then run O(n^2) LIS DP on it.
However, when I print the order and the sizes of all boxes, I found something weird:
The Bubble sort algorithm gave correct sorting order:
But std::sort gave wrong sorting order (more specific, box 5 should stay before box 1):
std::stable_sort also gave wrong sorting order:
Did something go wrong with my implementation? Or something went wrong with std::sort and std::stable_sort?