Implementation of sort - List

Kanashin (2)
Hello !

I want to do my own implementation of sort using the standard library of <list>.
I know how to implement merge sort if I have implemented my own list using nodes.

Could you, please, help me translating my code to the standard <list> of C++ ? I think that I have to use list<my_class>::iterator it to implement sort.

Thank-you for any help and I'm sorry for my orthography but I'm from Spain.

This is my code using my nodes:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
 
struct node {
   T info;
   node* next;
};

list<my_class> merge(list<my_class> L1, list<my_class> L2) {

    if (L1 == NULL) return L2;
    if (L2 == NULL) return L1;
   
    if (L1 -> info <= L2 -> info) {
       L1 -> next = merge(L1 -> next, L2)
       return L1;
    }
    else {
       L2 -> next = merge(L1, L2 -> next);
       return L2;
    }
   
}

void split(list<my_class>& L1, list<my_class>& L2, int m){
    node* p = L1;
    while (m > 1) {
        p = p -> next;
        --m;
    }
    L2 = p -> next;
    p -> next = NULL;
}

void mergesort (list<my_class>& L, int n) {
    if (n <= 1) return;
    int m = n / 2;
    list<my_class> aux = NULL;

    split(aux, aux, m);
   
    mergesort(L, m);
    mergesort(aux, n - m);
   
    aux = merge(L, aux);
}
Last edited on
kempofighter (1183)
Well I am not sure why you want to do such a thing when list already has its own sort and merge member functions. There are also numerous std algorithms that already implement this behavior using iterators.
http://cplusplus.com/reference/algorithm/
http://cplusplus.com/reference/stl/list/
Last edited on
Kanashin (2)
Thank-you very much for your answer.

I want to implement my own algorithm of sort. I want to do the same thing that list.sort(bool) but that sort implemented by me.
Topic archived. No new replies allowed.