# Mergesort Not Sorting Correctly

Page 1 of 1

## 4 Replies - 614 Views - Last Post: 24 August 2014 - 10:33 AMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'https://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=352507&amp;s=3f001470ea6388e8e7ab1a47cfe60b0d&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 yolo

Reputation: 0
• Posts: 1
• Joined: 23-August 14

# Mergesort Not Sorting Correctly

Posted 23 August 2014 - 01:48 PM

code:
```def merge_sort(list,i,j,new_list):
'''
(list,int,int) -> list

modifies and sorts 'list' showing steps and returns list

>>> merge_sort([3,2,-4,6,5], 0, len([3,2,-4,6,5]),[0]*len([3,2,-4,6,5]))

'''

if j-i <= 1:
return []

n = (i+j)//2

merge_sort(list,i,n,new_list)
merge_sort(list,n,j,new_list)

merge(list,i,j,new_list)

return new_list

def merge(list,i,j,new_list):
'''
(list,int,int,list) -> None

merges two sub lists in an order
'''

n = (i+j)//2
i1 = i
j1 = n
i2 = n
j2 = j

while i1 < j1 and i2 < j2:
if list[i1] < list[i2] :
new_list[i] = list[i1]
i1 = i1 + 1
else:
new_list[i] = list[i2]
i2 = i2 + 1
i = i + 1

while i1 < j1:
new_list[i] = list[i1]
i1 = i1 + 1
i = i + 1

while i2 < j2:
new_list[i] = list[i2]
i2 = i2 + 1
i = i + 1

return new_list

```

when I run it and type:
```>>> merge_sort([3,2,-4,6,5], 0, len([3,2,-4,6,5]),[0]*len([3,2,-4,6,5]))
[-4, 3, 2, 6, 5]
```

also, the merge() function seems to be working fine:
```>>> list = [2,6,9,3,6,8]
>>> merge(list,0,len(list),[0]*len(list))
[2, 3, 6, 6, 8, 9]
```

This post has been edited by macosxnerd101: 23 August 2014 - 01:51 PM
Reason for edit:: Renamed title to be more descriptive

Is This A Good Question/Topic? 0

## Replies To: Mergesort Not Sorting Correctly

### #2 andrewsw

• blow up my boots

Reputation: 6551
• Posts: 26,559
• Joined: 12-December 12

## Re: Mergesort Not Sorting Correctly

Posted 23 August 2014 - 03:19 PM

What should the output be?

You wrote this? So hopefully you should have some idea of where the problem is..?

And what do the four arguments to merge_sort represent?

### #3 DK3250

• Pythonian

Reputation: 407
• Posts: 1,313
• Joined: 27-December 13

## Re: Mergesort Not Sorting Correctly

Posted 24 August 2014 - 08:28 AM

In your call to the merge_sort function, don't do
```[0]*len([3,2,-4,6,5]
```

The values in your new_list becomes not five different zeros but rather the same zero times five. Change of one value will affect all.
You need to do something like:
```new_list = []
for i in range(len([...])):
new_list.append(0)
```

Another thing: Don't use the name <list> for a variable - list is a reserved word in Python; use <lst> or something else.

This post has been edited by DK3250: 24 August 2014 - 08:31 AM

### #4 sepp2k

• D.I.C Lover

Reputation: 2619
• Posts: 4,175
• Joined: 21-June 11

## Re: Mergesort Not Sorting Correctly

Posted 24 August 2014 - 10:17 AM

DK3250, on 24 August 2014 - 05:28 PM, said:

The values in your new_list becomes not five different zeros but rather the same zero times five.

That's not a meaningful distinction for integers.

Quote

Change of one value will affect all.

Except you can't perform any changes on integers. All you can do is reassign the array slot, which does not change anything except that array slot.

There's nothing wrong with [0] * n.

### #5 DK3250

• Pythonian

Reputation: 407
• Posts: 1,313
• Joined: 27-December 13

## Re: Mergesort Not Sorting Correctly

Posted 24 August 2014 - 10:33 AM

OK - I just had a similar situation with nested lists. And
```[[0]*10]*10
```

is certainly problematic.
I should have checked the details before posting.

Page 1 of 1

 .related ul { list-style-type: circle; font-size: 12px; font-weight: bold; } .related li { margin-bottom: 5px; background-position: left 7px !important; margin-left: -35px; } .related h2 { font-size: 18px; font-weight: bold; } .related a { color: blue; }