def testMerge(self):
     result = copy(self.original)
     before = time.time()
     merge_sort(result)
     after = time.time()
     print("Merge Sort, size: %d time: %f" % (self.list_length, after-before))
     self.assertEqual(self.sorted_list, result, "Merge Sort Failed")

def iterations(sort_type, n):  # This function sorts randomly generated numbers of length n that range from -500 to 500
	if sort_type == "selection sort":
		selection_sort.selection_sort([random.randint(-500,500) for number in range(n)])
	elif sort_type == "merge sort":
		merge_sort.merge_sort([random.randint(-500,500) for number in range(n)])
	elif sort_type == "quick sort":
		quick_sort.quick_sort([random.randint(-500,500) for number in range(n)])

def test_merge_sort(seq):
    """Test insertion sort results equal build-in python sort results."""
    from merge_sort import merge_sort
    seq = list(seq)
    sorted_copy = sorted(seq)
    merge_sort(seq)
    assert seq == sorted_copy

    def test_merge_sort_tests(self):
        '''Test the merge_sort function.'''
        # Test is_sorted
        for i in range(50):
            self.assertTrue(is_sorted(list(range(i))))
        
        # A basic example:
        L = [4,1,0,3,2]
        L = merge_sort(L)
        self.assertTrue(L == list(range(5)))

        # The empty list should be okay
        L = []
        L = merge_sort(L)
        self.assertTrue(L == [])

        # Hopefully it does nothing to already sorted lists:
        L = list('aeiou')
        L = merge_sort(L)
        s = ''.join(L)
        self.assertTrue(s == 'aeiou')

        # Does it shine with multisets?
        L = list('redrum')
        L = merge_sort(L)
        s = ''.join(L)
        self.assertTrue(s == 'demrru')

        # Do a few tests on lists of random integers
        for i in range(3,100):
            L = []
            for j in range(2,i):
                L.append(randint(1,j))
            L = merge_sort(L)
            self.assertTrue(is_sorted(L))

def sum_search(items, value):
  merge_sort.merge_sort(items, 0, len(items) - 1)
  for i in xrange(0, len(items)):
    last_item = items[-i-1]
    index = binary_search.binary_search(items, value - last_item, 0, len(items) - i - 1)
    if None != index:
      return (items[index], last_item)
  return None

def sum_exist(a,x):
	
	merge_sort(a,0,len(a)-1)
	##print a
	for i in range(len(a)):
		#binary_search(list,begin,end,key)
		if binary_search(a,i,len(a)-1,x-a[i]):
			return True
	return False

def test_stable():
    """Test identical items in list retain stable position on sort."""
    from merge_sort import merge_sort
    check_list = [1, 0, 2, 3, 2]
    two_a = check_list[2]
    two_b = check_list[4]
    merge_sort(check_list)
    assert check_list[2] is two_a
    assert check_list[3] is two_b

def test_stable_random(seq):
    """Test stability property on random lists."""
    from merge_sort import merge_sort
    seq = list(seq)
    index_a, index_b = sorted(random.sample(range(len(seq)), 2))
    val_a, val_b = -1, -1
    seq[index_a], seq[index_b] = val_a, val_b
    merge_sort(seq)
    assert seq[0] is val_a
    assert seq[1] is val_b

def test_stable_random_2(seq):
    """Test that stability fails when sorting to end of list."""
    from merge_sort import merge_sort
    seq = list(seq)
    index_a, index_b = sorted(random.sample(range(len(seq)), 2))
    val_a, val_b = 1000, 1000
    seq[index_a], seq[index_b] = val_a, val_b
    merge_sort(seq)
    assert seq[-1] is val_a
    assert seq[-2] is val_b

    def test_merge_sort(self):
        # reverse order input
        arr = [5, 4, 3, 2, 1]
        sorted_arr = merge_sort(arr)
        assert sorted_arr == [1, 2, 3, 4, 5]

        # already sorted
        arr = [1, 2, 3, 4, 5]
        sorted_arr = merge_sort(arr)
        assert sorted_arr == [1, 2, 3, 4, 5]

def choose_pivot(alist):
    medians = []
    index = 0
    length = len(alist)
    while length > index:
        sorted_group = merge_sort(alist[index:index + 5])
        medians.append(sorted_group[len(sorted_group) / 2])
        index += 5
      
    sorted_medians = merge_sort(medians)
   
    return sorted_medians[len(sorted_medians) / 2]

def test_stable_random_3(seq):
    """Test stability property on random lists with random duplicate values."""
    from merge_sort import merge_sort
    if len(seq) < 2:
        return
    seq = list(seq)
    index_a = random.randrange(len(seq) - 1)
    index_b = random.randrange(index_a + 1, len(seq))
    val_a = seq[index_a]
    val_b = int(val_a)
    seq[index_b] = val_b
    merge_sort(seq)
    index_a = seq.index(val_a)
    assert seq[index_a + 1] is val_b

def dselect(array, istat):
    if len(array) <= 5:  # should this be 10?
        sorted_array = merge_sort.merge_sort(array)
        return sorted_array[istat]
    else:
        groups_of_5 = []
        for group_start in range(0, len(array) - 4, 5):
            group = array[group_start:group_start + 5]
            group_median_pos = math.ceil(len(group) / 2) - len(group) % 2
            groups_of_5.append(dselect(group, int(group_median_pos)))
        median_of_medians = dselect(groups_of_5, len(array)//10)
        below = []
        above = []
        pivot = []
        for num in range(len(array)):
            if array[num] == median_of_medians:
                pivot.append(array[num])
            elif array[num] < median_of_medians:
                below.append(array[num])
            else:
                above.append(array[num])
        if istat < len(below):
            return dselect(below, istat)
        elif istat >= len(below) + len (pivot):
            return dselect(above, istat - len(below) - len(pivot))
        else:
            return median_of_medians

def search(arr, item):
    """Performs binary search on an array
    with the given item and returns True or
    False.
>>> search([5, 4, 1, 6, 2, 3, 9, 7], 2)
    True
>>> search([5, 4, 1, 6, 2, 3, 9, 7], 8)
    False
    """

    arr1 = merge_sort(arr)

    first = 0
    last = len(arr1) - 1
    found = False

    while first <= last and not found:
        midpoint = (first + last) // 2
        if arr1[midpoint] == item:
            found = True
        else:
            if item < arr1[midpoint]:
                last = midpoint - 1
            else:
                first = midpoint + 1

    return found

    def sort_merge(self):
        """Sorts the cards in this deck in ascending order

        Uses my my merge_sort"""
        if self.cards:
            self.cards = merge_sort(self.cards)
            return True
        else:
            return False

def run_all(input_directory, output_directory):
    if not os.path.exists(output_directory):
        os.makedirs(output_directory)

    def rel(filename):
        return os.path.join(output_directory, filename)

    # parse_xml(input_directory, rel('articles-raw.csv'), rel('citations-raw.csv'))
    # sanitize(rel('articles-raw.csv'), rel('articles-sanitized.csv'))
    unify_identifiers(rel("articles-sanitized.csv"), rel("articles-id-unified.csv"))
    merge_sort(rel("articles-id-unified.csv"), rel("articles-id-unified-sorted.csv"))
    return
    load_solr(rel("articles-id-unified-sorted.csv"))
    merge_solr(rel("articles-id-unified-sorted.csv"), rel("articles-solr-unified.csv"))
    merge_sort(rel("articles-solr-unified.csv"), rel("articles-solr-unified-sorted.csv"))
    combine_articles(rel("articles-solr-unified-sorted.csv"), rel("articles-tidy.csv"), rel("id-mapping.csv"))
    combine_articles(rel("articles-id-unified-sorted.csv"), rel("articles-tidy.csv"), rel("id-mapping.csv"))
    map_identifiers(rel("citations-raw.csv"), rel("citations-tidy.csv"), rel("id-mapping.csv"))

def test_sorting():
    import random
    datalist = [random.randint(0, 1e6) for i in xrange(100)]
    datalist = merge_sort(datalist)

    previous = datalist[0]
    for i in datalist[1:]:
        assert previous <= i
        previous = i

def test_stability():
    """A."""
    from merge_sort import merge_sort
    lst = [(2, 'ab'), (1, 'ba'), (3, 'ab'), (2, 'ba'), (5, 'ab')]
    one = lst[0]
    two = lst[3]
    sort_lst = merge_sort(lst)
    assert sort_lst == [(1, 'ba'), (2, 'ab'), (2, 'ba'), (3, 'ab'), (5, 'ab')]
    assert sort_lst[1] is one
    assert sort_lst[2] is two

def test_quick_sort(build_list):
    x, y = build_list
    assert quick_sort(x) == y

    import random
    for i in xrange(100):
        x = [random.randint(10,100) for i in xrange(20)]
        y = merge_sort(x)
        z = quick_sort(x)
        assert y == z

def find_dup_via_sort(array):
    """
    :type array: list of int
    :return the smallest duplicates
    """
    sorted_array = merge_sort.merge_sort(array)
    for i in range(len(sorted_array)):
        if i > 0:
            if sorted_array[i - 1] == sorted_array[i]: return sorted_array[i]
    return None