Median Calculation of List of Integers without using heap References

Using those references:


rolling median implementations benchmark
FAST RUNNING MEDIAN USING AN INDEXABLE SKIPLIST
Calculate the median of a billion numbers
Find running median from a stream of integers


Code

A code was written to calculate the Median with the SortedContainers library:

from itertools import islice
from sortedcontainers import SortedList
import random
import time

start_time = time.time()


class Median(object):

    def __init__(self, iterable):
        self._iterable = islice(iterable, None)
        self._sortedlist = SortedList(self._iterable)

    def __iter__(self):
        self_sortedlist = self._sortedlist
        # print(self_sortedlist)
        length = len(self_sortedlist)
        half = length // 2
        if length % 2 == 0:
            yield (self_sortedlist[half] + self_sortedlist[half - 1]) // 2
        elif length % 2 == 1:
            yield self_sortedlist[half]


def main():
    m, n = 1000, 1500000
    data = [random.randrange(m) for i in range(n)]
    # print("Random Data: ", data)
    result = list(Median(data))
    print("Result: ", result)


if __name__ == "__main__":

    main()
    print("--- %s seconds ---" % (time.time() - start_time))


Explanation

Random Number Generator

The following code generates data within the Range m and quantity n.

m, n = 1000, 15000000
data = [random.randrange(m) for i in range(n)]


Median

The Median class sorts the list of numbers and if n is odd, returns the middle item with yield self_sortedlist[half]. Or if n is even, returns the mean of two middle itens of the list with yield (self_sortedlist[half] + self_sortedlist[half - 1]) // 2

Question

How do I improve the code performance? Because for a large list (100 milion), it takes --- 186.7168517112732 seconds--- on my computer.
Performance
I instrumented your code differently:
def main():
    m, n = 1000, 15000000
    start_time = time.time()
    data = [random.randrange(m) for i in range(n)]
    print(&quot;--- %s seconds to generate&quot; % (time.time() - start_time))
    # print(&quot;Random Data: &quot;, data)
    start_time = time.time()
    result = SortedList(data)
    print(&quot;--- %s seconds to sort&quot; % (time.time() - start_time))
    start_time = time.time()
    result = list(Median(data))
    print(&quot;Result: &quot;, result)
    print(&quot;--- %s seconds ---&quot; % (time.time() - start_time))

For me, the results were:
--- 7.407598257064819 seconds to generate
--- 4.535749673843384 seconds to sort
Result:  [500]
--- 5.01109504699707 seconds ---

This shows that the generation of the random input takes longer than finding the median, and that 90% of Median() is spent sorting (probably most of the rest is caused by converting between lists and iterators).  You're unlikely to get large gains through modifications to your own part of the code.
I got better results by using Python's built-in sorted().  We don't need any of the extra functionality of SortedList (maintaining the invariant through adds and deletes), and a single sort (mostly in native code) gives these results:
def median(values):
    sortedlist = sorted(values)
    length = len(sortedlist)
    half = length // 2
    # return not yield; see &quot;General review&quot;
    if length % 2 == 0:
        return (sortedlist[half] + sortedlist[half - 1]) // 2
    else:
        return sortedlist[half]

def main():
    m, n = 1000, 15000000
    start_time = time.time()
    data = [random.randrange(m) for i in range(n)]
    print(&quot;--- %s seconds to generate&quot; % (time.time() - start_time))
    # print(&quot;Random Data: &quot;, data)
    start_time = time.time()
    result = sorted(data)
    print(&quot;--- %s seconds to sort&quot; % (time.time() - start_time))
    start_time = time.time()
    result = median(data)
    print(&quot;Result: &quot;, result)
    print(&quot;--- %s seconds ---&quot; % (time.time() - start_time))

--- 7.638948202133179 seconds to generate
--- 3.118924617767334 seconds to sort
Result:  500
--- 3.3397886753082275 seconds ---


General review
I don't see why you yield a single value, rather than simply returning.  Is there a need for Median() to be iterable?
Given that length is an integer, if length % 2 is not 0, it must be 1 - so the elif could easily be else.