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

Source: codewars | Difficulty: EASY
Tags: Sorting

Data structures

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):
	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()