There are two solutions, these being one to use javascript and one to use PHP.
Pure Javascript Solution:
Here is how to sort your <li> based on the data-date attribute. 
I've included both date based and string based sorting. 
JSFiddle: http://jsfiddle.net/xZaeu/
<html>
<script type="text/javascript" src="http://ajax.googleapis.com/ajax/libs/jquery/1.3/jquery.min.js"></script>
<body>
<ul id="ulList">
<li><a data-date="2013-09-16 11:44:50" href="http://example.com/url/">09!</a></li>
<li><a data-date="2013-08-16 11:44:50" href="http://example.com/url/">08!</a></li>
<li><a data-date="2013-07-16 11:44:50" href="http://example.com/url/">07!</a></li>
<li><a data-date="2013-11-16 11:44:50" href="http://example.com/url/">11!</a></li>
<li><a data-date="2013-10-16 11:44:50" href="http://example.com/url/">10!</a></li>
<li><a data-date="2013-06-16 11:44:50" href="http://example.com/url/">06!</a></li>
</ul>
<script>
function compareDataDates(a,b)
{
    var match = a.match(/^(\d+)-(\d+)-(\d+) (\d+)\:(\d+)\:(\d+)$/);
    var date1 = new Date(match[1], match[2] - 1, match[3], match[4], match[5], match[6]);
    match = b.match(/^(\d+)-(\d+)-(\d+) (\d+)\:(\d+)\:(\d+)$/);
    var date2 = new Date(match[1], match[2] - 1, match[3], match[4], match[5], match[6])
    return date1 - date2;
}
var list = $('#ulList');
var listItems = list.find('li').sort(function (a, b) {
        return compareDataDates($(a).find('a').eq(0).attr("data-date"), $(b).find('a').eq(0).attr("data-date"));
        //return $(a).find('a').eq(0).attr("data-date").localeCompare($(b).find('a').eq(0).attr("data-date"));
    });
list.find('li').remove();
list.append(listItems);
</script>
</body>
</html>
Both String and date comparison work since your using the specific format, though the string based comparison would fail in a situation where you have:
<li><a data-date="2013-06-16 11:44:50" href="http://example.com/url/">06!</a></li>
<li><a data-date="2013-6-16 11:44:50" href="http://example.com/url/">6!</a></li>
References used cooking this up:
Pure PHP Solution:
Something along the lines of...
   <?php
    //Other PHP code here...
   $arrayForSorting = new array();
   foreach ($notifications as &$value) 
   {
      $temp = addslashes($value);
      array_push($arrayForSorting,"<li>".$temp."</li>");  
   }
   //Sort the array
   asort($arrayForSorting);
   foreach ($arrayForSorting as &$value) 
   {
     echo $value;
   }
   ?>
References: