merge two list

[Progesco]

Please anyone give me a hint to merge 2 ordered list object (without using STL)
Thank you

[Zhuge]

What have you written so far?

[Progesco]

I just write a function to create list.
I'm thinking of run from 1st to last element of first list, and insert them to appropriate postion in second list. However, in this way, sorted objects seem to be useless

[melkiy]

When forming new list hold two pointers in the two initial lists, that point to current element in each list. Then move concurrently through these lists and what the element is smaller, add it to the resulting list and move forward the pointer.

[R0mai]

See std::merge's reference page :
http://www.cplusplus.com/reference/algorithm/merge/
There is it's implementation

[herbert1910]

I'm thinking of run from 1st to last element of first list, and insert them to appropriate postion in second list. However, in this way, sorted objects seem to be useless

your idea works if you never compare list1 to anything earlier than your last insertion in list2. since they are both sorted, you can run through each list once!

if you run out of elements in list2, stick the remainder of list1 on the end of list2. another benefit of sorted lists!

list1: *1 5 9 12
list2: *2 3 8
list2: (1) *2 3 8

list1: *5 9 12
list2: 1 *2 3 8
no insert
  
list1: *5 9 12
list2: 1 2 *3 8
no insert
  
list1: *5 9 12
list2: 1 2 3 *8
list2: 1 2 3 (5) *8

list1: *9 12
list2: 1 2 3 5 *8
no insert

list1: *9 12
list2: 1 2 3 5 8 * out of elements! stick on everything else.
list2: 1 2 3 5 8 (9 12)

list1:
list2: 1 2 3 5 8 9 12

merging may be easier to understand with a third list for the output. compare the lowest elements of list1 and list2, then move the lowest to list3. continue until you run out of elements.