-1

The question is :

Write a function called merge that takes two already sorted lists of possibly different lengths, and merges them into a single sorted list, without using the inbuilt sort function

I tried :

list1=(input("Enter the elements of list :")).split()
list2=(input("Enter the elements of list :")).split()

merged_list,sorted_list=(list1+list2),[]

#Without using sort()method 

def merge(list1,list2):

    global merged_list,sorted_list

    if len(merged_list)==0 : return sorted_list

    sorted_list.append(min(merged_list))

    merged_list.remove(min(merged_list))

    merge(list1,list2)

print(merge(list1,list2))

This gives output as "None", I don't know why. Also, it works well for alphabetic strings, but doesn't work for numerics, For example, if you give [02,1,0123] ,it returns [0123,02,1]. What should I change to make it work for both strings and numbers?

218 Mani kumar
  • 9
  • 5
  • 1
    Think about what happens the first time through. `merged_list` is not empty, so you don't return. You tweak the two lists, then call `merge` again, then fall through and return nothing. You need to use `return merge(list1,list2)`. BTW, this is not the correct way to solve this problem. Recursion is absolutely not needed. and you never use `list1` or `list2 `in your function, so why pass them? – Tim Roberts Jun 26 '23 at 02:48
  • @Tim Roberts When the merged_list goes empty, the if condition satisfies and must return sorted_list right? I don't see any mistake in my code. Could you please elaborate? And I know I can solve it without using recursion, I just want to know the mistake. – 218 Mani kumar Jun 26 '23 at 02:55
  • Is there a requirement to make a recursive function. This would typically (and more efficiently) be done with a simple loop. – Mark Jun 26 '23 at 02:57
  • @Mark Yeah I know and I did get output for strings when I used a simple while loop. But I just want to know what's wrong here, why does it return None? – 218 Mani kumar Jun 26 '23 at 02:59
  • Yeah, as Tim mentioned, the main issues is that when you write a recursive function you need to return the recursive call. – Mark Jun 26 '23 at 03:00
  • Right. When the list goes to zero, the innermost call returns a value. That returns to the next outermost call to `merge` at the last line of `merge`, and that does NOT return a value. See, `merge` calls `merge` calls `merge` calls `merge`. The final one has a return. The others don't. I told you how to fix it. – Tim Roberts Jun 26 '23 at 03:02
  • And as for your ordering, that's strictly a matter of definition. The string "0123" certainly is less than the string "02". If you want things ordered as numbers, you must convert them to numbers BEFORE you sort. Your function will work if you pass a list of integers. It's not the sort function's job to decide that. What if I sorted `["0123","02","abc","ghj"]`? – Tim Roberts Jun 26 '23 at 03:05
  • @Tim Roberts Yep I got it. Thanks so much. – 218 Mani kumar Jun 26 '23 at 03:12
  • FWIW, you also don't need the global variable — this can be done without it. In mutating general global variables should be avoidable without a _really_ good reason. – Mark Jun 26 '23 at 03:14
  • @Tim Roberts Where exactly should I include the line "return merge(list1, list2)"? – 218 Mani kumar Jun 26 '23 at 03:14
  • You replace the final line of the function (`merge(list1,list2)`). – Tim Roberts Jun 26 '23 at 03:19
  • @Tim Roberts About making the code work for both strings and numbers, is it not possible to make it universal? Should I really have to convert them into numbers before sorting or is there any other way? Like sorting every string according to their ASCII code or anything – 218 Mani kumar Jun 26 '23 at 03:24
  • The problem with strings vs numbers is that we expect the sort to work differently. We expect `z` to come after `abcd`, but we expect `9` to come before `1234`. – Mark Jun 26 '23 at 03:29
  • Yes, but you don't understand what you're asking. Your function works with strings. It also works with integers. It works with strings that contain digits, but not in the way you're thinking. When you pass it strings, they ARE sorted according to their ASCII order. Think about it. If you have "abcd" and "ac", it's clear that "abcd" comes first, right? That's EXACTLY the same as "0123" and "02". In ASCII order, the "0123" comes first. If YOU intended that those be integers, then convert them to integers. It's not the sort routine's fault. – Tim Roberts Jun 26 '23 at 03:30
  • Think about the strings `["x9x", "x88x", "x777x"]`. Do you expect the "x9x" to come first? Why? By ASCII ordering, "x777x" is first. Now, there ARE sort routines that would return "x9x" first (the WIndows File Explorer sorts that way), but that takes work. You have to convert the strings to a data structure that has the digits converted to integers. – Tim Roberts Jun 26 '23 at 03:32
  • So I must convert them into integers. There is no other way right..? A single code cannot work for both strings and numbers. I must write another code for numbers – 218 Mani kumar Jun 26 '23 at 03:36
  • @Tim Roberts How to do that? "Converting strings to a data structure" thing. Could you explain briefly – 218 Mani kumar Jun 26 '23 at 03:37
  • *A single code cannot work for both strings and numbers* -- OF COURSE IT CAN, as we have all been saying. Part of the problem is your terminology. The word "numbers" is ambiguous. Your code works for strings (`['aa','bb','cc']`) and it works for integers (`[111,222,333]`). It also works for strings that contain digits (which are still just strings), but it sorts them in ASCII order. That's the contract, and that's what the vast majority of sort operations do. – Tim Roberts Jun 26 '23 at 03:50
  • What you're asking for is called "natural sort order". You can search for algorithms. https://en.wikipedia.org/wiki/Natural_sort_order – Tim Roberts Jun 26 '23 at 03:55
  • 3
    Does this answer your question? [Why does my recursive function return None?](https://stackoverflow.com/questions/17778372/why-does-my-recursive-function-return-none) – chrslg Jun 26 '23 at 04:13

1 Answers1

0

This isn't exactly what you are asking, but I'll add this as an example of:

  1. returning from the recursive calls
  2. avoiding the unnecessary global variable

:

def merge(list1,list2):
    # base case: one or both are empty lists
    if len(list1) == 0 or len(list2) == 0:
        return list1 + list2
    
    if list1[0] < list2[0]:
        return [list1[0]] + merge(list1[1:], list2)
    else:
        return [list2[0]] + merge(list1, list2[1:])

    
list1 = [1, 4, 6, 8, 14, 22]
list2 = [1, 2, 5, 9, 10, 15, 18, 20]

merge(list1,list2)
# [1, 1, 2, 4, 5, 6, 8, 9, 10, 14, 15, 18, 20, 22]
Mark
  • 90,562
  • 7
  • 108
  • 148