As for lists vs. vectors, I think lists are more appropriate for me, since the indexes, as you see, aren't linear, they are sorted by position on the screen, so the [] operator doesn't really help me, since the index of the Event is irrelevant to its' position in the list and needs to be sought for either way, and like you see here, and it's the same in alot of other places in the code too, there's constant need to add and remove objects, which, to my understanding, a list does better.
[/quote]
std::vector is cache friendly and can be faster for adding/removing new elements, if you use the "swap and pop" trick or the "remove/erase" idiom. std::list is expensive due to the dynamic allocations it requires.

Here is my attempt to cleanup your code into simpler algorithms. I did this in two passes. The first was a simple cleanup where I tried to figure out what each loop was doing, and separated the loops from the others by removing shared variables. I also tried to clarify certain situations, like where you are testing for a single element list.

This was the result of the first pass:

#include <list>

struct Event
{
int y;
int index;
int solid;
};

struct Character
{
int y;
int drawPos;
};

typedef std::list<Event> EventList;
typedef EventList::const_iterator EventListIterator;

EventList sortEvents(EventList &evList, Character &hero)
{
if(evList.empty())
{
return evList;
}

if(evList.size() == 1)
{
Event event = evList.front();
if(hero.y > event.y)
{
hero.drawPos = 1;
}
else
{
hero.drawPos = 0;
}
return evList;
}

EventList overList;
EventList underList;

for(EventListIterator it = evList.begin() ; it != evList.end() ; /* ... */)
{
if(it->solid == 1)
{
underList.push_back(*it);
evList.erase(it);
it = evList.begin();
}
else if(it->solid == 2)
{
overList.push_back(*it);
evList.erase(it);
it = evList.begin();
}
else
{
it++;
}
}

if(evList.empty())
{
hero.drawPos = 0;
}
else
{
if(evList.size() == 1)
{
const Event &event = evList.front();

if(hero.y > event.y)
{
hero.drawPos = 1;
}
else
{
hero.drawPos = 0;
}
}
else
{
hero.drawPos = -1;
}

EventListIterator it1 = evList.begin();
EventListIterator it2 = it1;
it2++;

for(int i = 0; it2 != evList.end(); i++)
{
if(it1->y > it2->y)
{
evList.insert(it1, it2);
evList.erase(it2);
it1 = evList.begin();
it2 = it1;
i = 0;
}
else
{
if(hero.y >= it1->y && hero.y <= it2->y)
{
hero.drawPos = i + 1;
}
else if(hero.y > it2->y)
{
hero.drawPos = i + 2;
}

if(it1 != evList.end())
{
++it1;
}

}
++it2;
}

}

for(EventListIterator it = overList.begin() ; it != overList.end() ; ++it)
{
evList.push_back(*it);
}

for(EventListIterator it = underList.begin() ; it != underList.end() ; ++it)
{
evList.push_front(*it);
hero.drawPos++;
}

return evList;
}


Using this as a base, I tried to decouple the two things you were doing in this function. One was sorting the event list, and the other was determining the hero's draw position.

I replaced the hand written logic with standard library calls. This is a pre C++0x version.

#include <list>
#include <iterator>
#include <algorithm>

struct Event
{
int y;
int index;
int solid;
};

struct Character
{
int y;
int drawPos;
};

typedef std::list<Event> EventList;
typedef EventList::const_iterator EventListIterator;

struct EventSorter
{
bool operator()(const Event &a, const Event &b) const
{
if(a.solid == b.solid)
{
return a.y < b.y;
}
static const int lookup[] = {1, 0, 2};
return lookup[a.solid] < lookup[b.solid];
}
};

void doSortEvents(EventList &events)
{
events.sort(EventSorter());
}

struct HeroDrawPositionLocator
{
public:
HeroDrawPositionLocator(Character &hero)
:
hero(&hero)
{
}

bool operator()(const Event &event) const
{
if(event.solid != 0)
{
return false;
}
return event.y > hero->y;
}
private:
Character *hero;
};

void setHeroDrawPosition(const EventList &events, Character &hero)
{
EventListIterator it = std::find_if(events.begin(), events.end(), HeroDrawPositionLocator(hero));

if(it != events.end())
{
int i = std::distance(events.begin(), it);
hero.drawPos = i + 1;
}
else
{
hero.drawPos = -1;
}
}

void sortEvents(EventList &events, Character &hero)
{
doSortEvents(events);
setHeroDrawPosition(events, hero);
}


In C++0x (available in modern compilers such as MS Visual C++ 2010), we can use lambda functions to inline the searching/sorting predicates:

#include <list>
#include <iterator>
#include <algorithm>

struct Event
{
int y;
int index;
int solid;
};

struct Character
{
int y;
int drawPos;
};

typedef std::list<Event> EventList;
typedef EventList::const_iterator EventListIterator;

void doSortEvents(EventList &events)
{
events.sort([](const Event &a, const Event &b) -> bool {
if(a.solid == b.solid)
{
return a.y < b.y;
}
static const int lookup[] = {1, 0, 2};
return lookup[a.solid] < lookup[b.solid];
});
}

void setHeroDrawPosition(const EventList &events, Character &hero)
{
EventListIterator it = std::find_if(events.begin(), events.end(), [&hero](const Event &event) -> bool {
if(event.solid != 0)
{
return false;
}
return event.y > hero.y;
});

if(it != events.end())
{
int i = std::distance(events.begin(), it);
hero.drawPos = i + 1;
}
else
{
hero.drawPos = -1;
}
}

void sortEvents(EventList &events, Character &hero)
{
doSortEvents(events);
setHeroDrawPosition(events, hero);
}

They say most programs spend all their time searching and sorting. It is a good idea to separate the search/sort "predicate" (the logic which determines if you've found the right object, or if something is out of order) from the logic which performs the search/sort itself.

Apart from the shorter, more readable code, another advantage is performance. Your custom sort loop is pretty much the worst way to perform a sort. It resulted in lots (and lots) of unnecessary work. Your game was probably slowing down very quickly simply due to the poor algorithm in use, and also the excessive dynamic allocation involved.

I may have made some mistakes during this process, so were I you I'd write some unit tests for the functions to ensure they act correctly under different circumstances.