Python - Searching and Sorting(merge sort, algorithm)

Practical Programming
An Introduction to Computer Science
Using Python 3
(Pragmatic Programmers)
(Pragmatic Bookshelf)
Paul Gries (著) Jennifer Campbell (著)
Jason Montojo (著) Lynn Beighley (編集)

開発環境

• OS X Yosemite - Apple (OS)
• Emacs (CUI)、BBEdit - Bare Bones Software, Inc. (GUI) (Text Editor)
• Python 3.4 (プログラミング言語)

Practical Programming: An Introduction to Computer Science Using Python 3 (Pragmatic Programmers) (Paul Gries (著)、Jennifer Campbell (著)、Jason Montojo (著)、Lynn Beighley (編集)、Pragmatic Bookshelf)のChapter 13(Searching and Sorting)、13.7(Exercises) 10.を解いてみる。

13.7(Exercises) 10.

コード(BBEdit)

sample10.py

#!/usr/bin/env python3
#-*- coding: utf-8 -*-

def merge(L1, L2):
    """ (list, list) -> list
    Merge sorted lists L1 and L2 into a new list and return that new list.
    >>> merge([1, 3, 4, 6], [1, 2, 5, 7])
    [1, 1, 2, 3, 4, 5, 6, 7]
    """
    newL = []
    i1 = 0
    i2 = 0
    while i1 != len(L1) or i2 != len(L2):
        if i2 == len(L2) or (i1 != len(L1) and L1[i1] <= L2[i2]):
            newL.append(L1[i1])
            i1 += 1
        else:
            newL.append(L2[i2])
            i2 += 1
    return newL

def mergesort(L):
    """ (list) -> NoneType
    Reorder the items in L from smallest to largest.
    >>> L = [3, 4, 7, -1, 2, 5]
    >>> mergesort(L)
    >>> L
    [-1, 2, 3, 4, 5, 7]
    """
    workspace = []
    for i in range(len(L)):
        workspace.append([L[i]])
    i = 0
    while i < len(workspace) - 1:
        L1 = workspace[i]
        L2 = workspace[i + 1]
        newL = merge(L1, L2)
        workspace.append(newL)
        i += 2
    if len(workspace) != 0:
        L[:] = workspace[-1][:]

if __name__ == '__main__':
    import doctest
    doctest.testmod()

入出力結果(Terminal, IPython)

$ ./sample10.py -v
Trying:
    merge([1, 3, 4, 6], [1, 2, 5, 7])
Expecting:
    [1, 1, 2, 3, 4, 5, 6, 7]
ok
Trying:
    L = [3, 4, 7, -1, 2, 5]
Expecting nothing
ok
Trying:
    mergesort(L)
Expecting nothing
ok
Trying:
    L
Expecting:
    [-1, 2, 3, 4, 5, 7]
ok
1 items had no tests:
    __main__
2 items passed all tests:
   1 tests in __main__.merge
   3 tests in __main__.mergesort
4 tests in 3 items.
4 passed and 0 failed.
Test passed.
$