Alphabetical MergeSort Based on a Last Name

Question

I need to write a mergeSort function that will merge two files, and sort the lists contained in the files in alphabetical order based on a word in the list. The file will look something like this once merged:

['Bud', 'Abbott', 51, 92.3]
['Mary', 'Boyd', 52, 91.4]
['Jill', 'Carney', 53, 76.3]
['Jeff', 'Zygna', 50, 82.1]
['Don', 'Adams', 51, 90.4]
['Randy', 'Newman', 50, 41.2]
['Fred', 'Quicksand', 51, 88.8]
['John', 'Ziley', 53, 90.1]

The lists are arranged in the order: firstName, lastName, course, grade. What I am attempting to do is sort the lists in alphabetical order based on the last name after merging them. How would I begin to do that?

Does it actually need to implement the merge sort algorithm? — Tomasz Kaminski, Nov 28 '15 at 20:52

Marco Bonelli · Answer 1 · 2015-11-28T21:16:24.563

Assuming you have the list of lists:

people = [
    ['Bud', 'Abbott', 51, 92.3],
    ['Mary', 'Boyd', 52, 91.4],
    ['Jill', 'Carney', 53, 76.3],
    ['Jeff', 'Zygna', 50, 82.1],
    ['Don', 'Adams', 51, 90.4],
    ['Randy', 'Newman', 50, 41.2],
    ['Fred', 'Quicksand', 51, 88.8],
    ['John', 'Ziley', 53, 90.1]
]

You can sort it by surname (i.e. the second element of each list) using the standard sorted function and providing a key function to extract the surname from the list and use it as a comparison term.

Here's all you need:

people_ordered = sorted(people, key = lambda x: x[1])

If you want to modify the existing list, you can also use the .sort() method instead:

people.sort(key = lambda x: x[1])

`operator.itemgetter(1)` would be better than a lambda – Padraic Cunningham Nov 29 '15 at 00:25 — Padraic Cunningham, Nov 29 '15 at 00:25

score 1 · Answer 2 · answered Nov 28 '15 at 21:04

The other answers already point out how to sort lists of lists based on on a particular index within each element list. If you have to merge by hand, though:

target_list = []
counter1, counter2 = 0, 0
while counter1 < len(list1) or counter2 < len(list2):
    if counter1 == len(list1):
        target_list.extend(list2[counter2:])
        break
    if counter2 == len(list2):
        target_list.extend(list1[counter1:])
        break
    if list1[counter1][1] <= list2[counter2][1]:
# the '<=' seems arbitrary, but ensures sort stability in a recursive sort  
# where list1 is the sorted lower half of a previous split
        target_list.append(list1[counter1])
        counter1 += 1
    else:
        target_list.append(list2[counter2])
        counter2 += 1

Dušan Maďar · Answer 3 · 2015-11-28T21:11:59.740

Tell the sort function which list item (key) it should use for sorting.

from pprint import pprint

merged = [
    ['Bud', 'Abbott', 51, 92.3],
    ['Mary', 'Boyd', 52, 91.4],
    ['Jill', 'Carney', 53, 76.3],
    ['Jeff', 'Zygna', 50, 82.1],
    ['Don', 'Adams', 51, 90.4],
    ['Randy', 'Newman', 50, 41.2],
    ['Fred', 'Quicksand', 51, 88.8],
    ['John', 'Ziley', 53, 90.1]
]

merged.sort(key=lambda x: x[1])
pprint(merged)
>>> [['Bud', 'Abbott', 51, 92.3],
     ['Don', 'Adams', 51, 90.4],
     ['Mary', 'Boyd', 52, 91.4],
     ['Jill', 'Carney', 53, 76.3],
     ['Randy', 'Newman', 50, 41.2],
     ['Fred', 'Quicksand', 51, 88.8],
     ['John', 'Ziley', 53, 90.1],
     ['Jeff', 'Zygna', 50, 82.1]]

Please be aware that sort() sorts the list in place, while sorted() creates a new list. For more info refer to documentation: Sorting HOW TO.

Alphabetical MergeSort Based on a Last Name

3 Answers3