Как да сортирам масив от поддокументи в mongoose/mongodb?

Трябва да използвате $sort с $each и след това просто посочвате името на вложеното поле (а не целия път, както във вашия пример), опитайте:

User.findOneAndUpdate({ _id: user._id }, { 
    $push: {
        "notification.notidata": {
            "$each": [ { data: { para: "Your Ad " + "'" + thisad.heading + "'" + " has been successfully submitted." } } ],
            "$sort": {"notidate": -1}
        }
    }
}, {new: true})