1

I have a list of integers, all split into k sub-lists until the length of each sub-list is 1. My goal is to use a sorting algorithm that takes parameters of k and a sorted list of length > 0 (e.g. list = [[1, 4, 8], [2, 3, 7], [5, 6, 9]]). For example:

list = [[[5], [2], [4]], [[9], [1], [8]], [[7], [6], [3]]]
k = 3

After applying the sorting algorithm:

list = [[2, 4, 5], [1, 4, 9], [3, 6, 7]]

After applying the sorting algorithm:

list = [1, 2, 3, 4, 5, 6, 7, 8, 9]
print('Sorted list: ', list)

I've tried iterating through the lowest level sub lists log(len(list), k) but just end up getting stuck in recursive loops. I'm not very experienced in python and feel like there would be some sort of shortcut.

EDIT: I know this is a lot of code but I don't know how else to explain myself:

from math import *
input_list = [[[5], [2], [4]], [[9], [1], [8]], [[7], [6], [3]]]
result = []
numbers = 9
k = 3
new_list = []

def merge(k, list):#---------------for list [[ordered], [ord..], [ord..]]
    global result
    while len(list) > 0:
        b = 0
        low = min(list)
        x = list.index(low)

        for sub_list in list:
            if b == x:
                result.append(sub_list[b])
                sub_list.pop(0)
                list = [x for x in list if x != []]

            b+=1
    print('Final list: ', list)
    print('Final result: ', result)

def split_list(input_list, k):
    if len(input_list) == 1:
        return input_list
    segment = len(input_list) // k
    return [split_list(input_list[i:i+segment], k) 
            for i in range(0, len(input_list), segment)]


def merge_sort(k, list):
    iterations = log(numbers, k)
    a = 0
    for sub_list in list:
        if a < iterations:
            list = list[0]
            a += 1
        else:
            merge(k, sub_list)

list = split_list(input_list, k)
print(merge_sort(k, list))
print(list)

My merge() function works perfectly fine, however I don't know how to iterate through an unknown number of sub-lists for my merge_sort() to work.

EDIT 2: In reference to the flatten suggestion, I'm still looking into it but I don't think this will help my situation. In my merge function the sub-lists are flattened by the end. For example:

k = 3
list = [[5], [2], [4]]
print(merge(k, sub_lists))

Would produce an output of [2, 4, 5]

rn_pochno
  • 11
  • 2
  • 1
    This isn't a code-writing or tutorial service; where's your code, and what's the problem with it? – jonrsharpe Jan 14 '16 at 23:17
  • What is this, a mergesort? If it is, it's a weird way to go about it. – user2357112 Jan 14 '16 at 23:20
  • Yep, a mergesort, I'll edit and add code now, it's just difficult to narrow it down so it's not too long to put in a question. – rn_pochno Jan 14 '16 at 23:26
  • Why don't you use the builtin sort? – Karoly Horvath Jan 14 '16 at 23:47
  • This is part of an academic exercise demonstrating the use of a merge() function we had to write. What is the builtin sort? – rn_pochno Jan 14 '16 at 23:49
  • Possible duplicate of [Flattening a shallow list in Python](http://stackoverflow.com/questions/406121/flattening-a-shallow-list-in-python) – Prune Jan 15 '16 at 00:09
  • I believe that what you want first is what's called a "flatten" function. There are a number of such references in StackOverflow ... now that you have the term. – Prune Jan 15 '16 at 00:10

0 Answers0