Download code

From LiteratePrograms

Jump to: navigation, search

Back to Merge_sort_(Python)

Download for Windows: single file, zip

Download for UNIX: single file, zip, tar.gz, tar.bz2

mergesort.py

 1 # Copyright (c) 2010 the authors listed at the following URL, and/or
 2 # the authors of referenced articles or incorporated external code:
 3 # http://en.literateprograms.org/Merge_sort_(Python)?action=history&offset=20100310094841
 4 # 
 5 # Permission is hereby granted, free of charge, to any person obtaining
 6 # a copy of this software and associated documentation files (the
 7 # "Software"), to deal in the Software without restriction, including
 8 # without limitation the rights to use, copy, modify, merge, publish,
 9 # distribute, sublicense, and/or sell copies of the Software, and to
10 # permit persons to whom the Software is furnished to do so, subject to
11 # the following conditions:
12 # 
13 # The above copyright notice and this permission notice shall be
14 # included in all copies or substantial portions of the Software.
15 # 
16 # THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
17 # EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
18 # MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
19 # IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
20 # CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
21 # TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
22 # SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
23 # 
24 # Retrieved from: http://en.literateprograms.org/Merge_sort_(Python)?oldid=16663
25 
26 def merge(left, right):
27     result = []
28     i ,j = 0, 0
29     while i < len(left) and j < len(right):
30         if left[i] <= right[j]:
31             result.append(left[i])
32             i += 1
33         else:
34             result.append(right[j])
35             j += 1
36 
37     result += left[i:]
38     result += right[j:]
39     return result
40 
41 def mergesort(list):
42     if len(list) < 2:
43         return list
44     else:
45         middle = len(list) / 2
46         left = mergesort(list[:middle])
47         right = mergesort(list[middle:])
48         return merge(left, right)
49 
50 if __name__ == "__main__":
51     print mergesort([3, 4, 8, 0, 6, 7, 4, 2, 1, 9, 4, 5])
52


Retrieved from "http://en.literateprograms.org/Special:Downloadcode"
Views
Personal tools