Write a `sort` function that will sort a massive list of strings in caseless, lexographic order.

Example Input:
`['b', 'ba', 'ab', 'bb', 'c']`

Expected Output:
`['ab', 'b', 'ba', 'bb', 'c']`

* The argument for your function will be a generator that will return a new word for each call of next()
* Your function will return its own generator of the same words, except your generator will return the words in lexographic order
* All words in the list are unique
* All words will be comprised of lower case letters only (a-z)
* All words will be between 1 and 8 characters long
* There will be hundreds of thousands of words to sort
* You may not use Python's sorted built-in function
* You may not use Python's list.sort method
* An empty list of words should result in an empty list.
* `alphabet = 'abcdefghijklmnopqrstuvwxyz'` has been pre-defined for you, in case you need it

Difficulty: introductory

Starter code:

def sort(words):
	

Solutions:
import heapq, itertools

def sort(iterable):
    heap = list(iterable)
    heapq.heapify(heap)
    return (heapq.heappop(heap) for i in range(len(heap)))

def sort(words):
    from random import choice
    from itertools import chain
    words = list(words)
    if len(words) <= 1: return iter(words)
    pivot = choice(words)
    return chain(sort(w for w in words if w < pivot), [pivot], sort(w for w in words if w > pivot))

from heapq import *

def sort(iterable):
    h = []
    for value in iter(iterable):
        heappush(h, value)
    return iter([heappop(h) for i in range(len(h))])

def sort(arr):
    """ You'll have to try harder than that @sazlin """
    result = [a for a in arr]
    result.__getattribute__('sort')()
    yield from result

import heapq as hp

def sort(words):
    words = list(words)
    hp.heapify(words)
    while words:
        yield hp.heappop(words)

def sort(words):
    if not words: return
    it = iter(words)
    pivot = next(it)
    lt, ge = [], []
    for i in it:
        if i < pivot: lt.append(i)
        else: ge.append(i)
    yield from sort(lt)
    yield pivot
    yield from sort(ge)

from heapq import heapify, heappop

def sort(words):
    words = list(words)
    heapify(words)
    while words:
        yield heappop(words)

from itertools import chain

def merge_sort(words):
    if len(words) <= 1: return words
    midpt = len(words) // 2
    arr1 = merge_sort(words[:midpt])
    arr2 = merge_sort(words[midpt:])
    res = []
    
    while len(arr1) > 0 and len(arr2) > 0:
        if arr1[0] > arr2[0]:
            res.append(arr2.pop(0))
        else:
            res.append(arr1.pop(0))
    if len(arr1) > 0:
        res.extend(arr1)
    else:
        res.extend(arr2)
    return res
    

def sort(words):
    if not words: return []
    dict_by_alpha = dict()
    
    for a in alphabet:
        dict_by_alpha[a] = []
    for w in words:
        dict_by_alpha[w[0]] += [w]
    return chain.from_iterable(merge_sort(dict_by_alpha[a]) for a in alphabet)    


from heapq import heappush, heappop
def sort(words):
    heap = []
    for w in words: heappush(heap, w)
    while heap: yield heappop(heap)

import heapq

def sort(words):
    heap = []
    cnt = 0
    for w in words:
        cnt += 1
        heapq.heappush(heap, w)

    def sorted_gen():
        for i in range(cnt):
            yield heapq.heappop(heap)
    return sorted_gen()