Сортировка стека

[dzega]

Приветствую всех ! Есть код программы, сортирующей стек методом простых вставок, а нужно исправить программу на сортировку стека методом бинарных вставок. Спасибо Заранее !

#include <iostream>
#include <stdlib.h>

using namespace std;
#define NOTHING 0
template <class E> struct element{
E mean;
element *prev;
element *next;
};
template <class T> class stek{
element<T> *head;
element<T> *back;
element<T> *tmp;
int count;
public:
stek(){
head=NOTHING;
back=NOTHING;
tmp=NOTHING;
count=0;
}
bool PushFront(T elem){
if(elem==NOTHING)
return false;
tmp = new element<T>;
tmp->mean=elem;
tmp->prev=head;
tmp->next=NOTHING;
if(head==NOTHING){
back=tmp;
}
else{
head->next=tmp;
}
head=tmp;
count++;
return true;
}
bool PushBack(T elem){
if(elem==NOTHING)
return false;
tmp = new element<T>;
tmp->mean=elem;
tmp->prev=NOTHING;
tmp->next=back;
if(back==NOTHING){
head=tmp;
}
else{
back->prev=tmp;
}
back=tmp;
count++;
return true;
}
T PopFront(){
if(head==NOTHING)
return NOTHING;
T res=head->mean;
tmp=head;
head=head->prev;
if(head==back)
head->next=NOTHING;
delete tmp;
count--;
return res;
}
T PopBack(){
if(back==NOTHING)
return NOTHING;
T res=back->mean;
tmp=back;
back=back->next;
if(head==back)
back->prev=NOTHING;
delete tmp;
count--;
return res;
}

bool isEmpty(){
if(count==0)
return true;
else
return false;
}
void print(){
element<T> *t=back;
while(t!=NOTHING){
cout<<t->mean<<" ";
t=t->next;
}
}
};

int main() {
cout << "СoPTuPoBKa MeToDoM nPoCTblX BCTaBoK" << endl;
stek<int> *l=new stek<int>();
int gen;
srand;
//генерируем одно и 2х значные случайные числа (~50/50) исключая ноль
for(int i=0;i<15;i++){
gen=(rand()%10>5?rand()%100:rand()% 10);
l->PushBack(gen==0?NOTHING:gen);
}
l->print();
cout<<endl;
/* берем из основного cтека по кею,
* Вытаскиваем из временного стека по элементу,
* сравниваем с текущим кеем и засовываем в рез
* если текущий кей меньшечем текущий элемент тм,
* то засовываем сначала его, а потом все остальные,
* перекидываем все обратно в тм
* и переходим к следующей итерации (берем следующий элемент кей)
* ВНИМАНИЕ! нельзя чтобы в исходных данных был ноль - он испульзуется
* как ноль! (константа nothing) (АТД возвращает его когда не находит больше элементов)
*/
int key,key2;
stek<int> *tm=new stek<int>();
stek<int> *res=new stek<int>();
do {
key=l->PopFront();
do {
key2=tm->PopFront();
if(key>=key2){
res->PushFront(key);
res->PushFront(key2);
//докидываем оставшиеся
while(!tm->isEmpty()){
key2=tm->PopFront();
res->PushFront(key2);
}
}
else{
res->PushFront(key2);
}
} while(!tm->isEmpty());
//перегоняем обратно в тм
while(tm->PushFront(res->PopFront()));
}while(!l->isEmpty());

while(l->PushFront(tm->PopBack()));
l->print();

cin.get ();
}

[dzega]

Сортировка методом бинарных вставок:


1: void past_sort_bin(mat r[], int N)
2: {
3: int i, left, right, k, s;
4: mat x;
5:
6: for (i = 1; i < N; i++)
7: {
8: left = 0;
9: right = i;
10:
11: k = (right + left)/2;
12:
13: while (left != k)
14: {
15: if (r[k].code > r[i].code)
16: right = k;
17: else
18: left = k;
19: k = (right + left)/2;
20: }
21:
22: if (r[left].code < r[i].code)
23: {
24: if (r[i].code > r[k].code)
25: left = k+1;
26: else
27: left = k;
28: }
29:
30: x = r[i];
31:
32: for (s = i; s > left; s--)
33: r[s] = r[s-1];
34:
35: r[left] = x;
36: }
37: }


Я просто не могу убрать оттуда простые вставки и поставить бинарные. Не понимаю как связать