-1

I need to write a merge_sort and a corresponding merge_two_halves function which sorts the parameter list of tuples. The list should be sorted in reverse order (biggest-smallest). Each tuple in the list of tuples which is passed as a parameter to the merge_sort function contains two elements and the merge_sort function should use the first element (a string) of each tuple as the sort key.

such that:

def main():
    print("1.")
    a_list = [0, 0, 0, 0, 0]    
    list_of_tuples_left = [('Tim', 194493), ('Song', 201670), ('Abe', 203126)]
    list_of_tuples_right = [('Jim', 194169), ('Ben', 179619)]
    merge_two_halves(a_list, list_of_tuples_left, list_of_tuples_right)
    print(a_list)
    print()

    print("2.")
    a_list = [0, 0, 0, 0, 0, 0, 0, 0]   
    list_of_tuples_left = [('Joseph', 194493), ('Ethan', 201670), ('Christopher',
                            203126),('Andrew', 202301)]
    list_of_tuples_right = [('William', 194169), ('David', 179619), ('Anthony', 
                             191681), ('Alexander', 178646)]
    merge_two_halves(a_list, list_of_tuples_left, list_of_tuples_right)
    print(a_list)
    print()

    print("3.")
    names_id_tuples = get_list_of_tuples_from_file("namesId.txt")
    merge_sort(names_id_tuples)

    for i in range(30):
        print(names_id_tuples[i])

    print()

I don't even know where to begin with this. Any help would be awesome

Mike
  • 439
  • 1
  • 6
  • 13
Newbie
  • 378
  • 2
  • 12
  • 23
  • You should learn about `yield`, it makes a merge absolutely trivial. – Mark Ransom Oct 15 '14 at 20:17
  • try `heapq.merge()`. Wrap items using your custom `key()` function if necessary. See [Sorting text file by using Python](http://stackoverflow.com/q/14465154/4279) and [Improving merge sort](http://stackoverflow.com/q/15579226/4279). – jfs Oct 15 '14 at 23:01
  • You might consider re-editing existing code of merge sort algorithm on this case http://interactivepython.org/runestone/static/pythonds/SortSearch/TheMergeSort.html – user3378649 Oct 15 '14 at 23:51

1 Answers1

0

On the slides look for merge sort and just copy and paste that, it should have it for merge and merge_two_halves. Once you have that pasted below the def merge(?): and def merge_two_halves(?): then the only thing you need to change is one < to > in the merge_two_halves, you can try and figure out which one.

Mark
  • 2,380
  • 11
  • 29
  • 49
helper
  • 1