### Thread: Stitching two lists together

1. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Dec 2008
Posts
17
Rep Power
0

#### Stitching two lists together

say i have two sorted lists, list1 and list2. i would like to stitch these two lists together to another list, list3. This list would have all items on list1 and list2 sorted in order. How would i go about doing it? I think the way i approached this problem is wrong, below is my trial:

Code:
```    a, b, result = 0, 0, []

while a != len(list1) or b != len(list2):
if list1[a] <= list2[b]:
result.append(list1[a])
a += 1
else:
result.append(list2[b])
b += 1```
I would like to see a correct implementation so I can see which assumption is wrong in my approach
2. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Jul 2007
Location
Joensuu, Finland
Posts
471
Rep Power
70
Originally Posted by jepot
say i have two sorted lists, list1 and list2. i would like to stitch these two lists together to another list, list3.
Is it really necessary to “stitch” them together? If the lists aren’t inordinately long, the easiest way would be to combine them and then sort.

Code:
```>>> l1 = ['a', 'd', 'q']
>>> l2 = ['b', 'c', 'f']
>>> l1 + l2
['a', 'd', 'q', 'b', 'c', 'f']
>>> sorted(l1 + l2)
['a', 'b', 'c', 'd', 'f', 'q']```
Otherwise, at least if the lists are of equal length, you might do:

Code:
```l3 = []
for x, y in zip(l1, l2):
l3.append(x if x < y else y)
l3.append(y if x < y else x)```

• b49P23TIvg disagrees : [code]>>> l3 = [] >>> for x, y in zip([1,2,3], [4,5,6]): ... l3.append(x if x < y else y) ... l3.append(y if x < y else x) ... >>> l3 [1, 4, 2, 5, 3, 6][/code]
3. I'm astounded that my merge function performs almost as well as combining the lists, then using lists's sort method. p.py uses list.sort(), q.py uses merge. Timings and tests are shown.

p.py
Code:
```#\$ time python /tmp/p.py
#
#real	0m0.532s
#user	0m0.504s
#sys	0m0.020s

import random

N = 100000

def IsSorted(L):
'''
\$ python -m doctest p.py
>>> IsSorted(list('acx'))
True
>>> IsSorted(list('cax'))
False
'''
return all(x<=y for (x,y,) in zip(L[:-1],L[1:]))

a = list(random.random() for i in range(N))
b = list(random.random() for i in range(N))
a.sort()
b.sort()
c = a+b
c.sort()
assert IsSorted(c)```

q.py
Code:
```#\$ time python /tmp/q.py
#
#real	0m0.589s
#user	0m0.540s
#sys	0m0.040s

import random

N = 100000

def IsSorted(L):
'''
\$ python -m doctest p.py
>>> IsSorted(list('acx'))
True
>>> IsSorted(list('cax'))
False
'''
return all(x<=y for (x,y,) in zip(L[:-1],L[1:]))

a = list(random.random() for i in range(N))
b = list(random.random() for i in range(N))
a.sort()
b.sort()

def merge(a,b):
'''
>>> ''.join(merge(list('Abf'),list('CDEfnp')))
'ACDEbffnp'
'''
c = []
i = j = 0
La = len(a)
Lb = len(b)
while (i < La) and (j < Lb):
if a[i] < b[j]:
c.append(a[i])
i += 1
else:
c.append(b[j])
j += 1
if i < La:
c.extend(a[i:])
elif j < Lb:
c.extend(b[j:])
return c

c = merge(a,b)
c.sort()
assert IsSorted(c)```
4. (Point was to use SuperOscar's second code with the lists
[1,2,3] and [4,5,6])