# -*- coding: utf-8 -*-

"""
:mod:`sorting` module : sorting functions module for experience assignment

:author: `Dpt Informatique - FST - Univ. Lille <http://portail.fil.univ-lille1.fr>`

:date: 2018, january
"""

import copy
import numpy

def merge (t1,t2, cmp):
    """
    Given two sorted array, creates a fresh sorted array.
    
    :param t1: An array of objects
    :type t1: Array
    :param t2: An array of objects
    :type t1: Array
    :param cmp: A comparison function, returning 0 if a == b, -1 is a < b, 1 if a > b
    :type cmp: function
    :return: A fresh array, sorted.
    :rtype: array
    
    .. note::
    
       time complexity of merge is :math:`O(n_1+n_2)` with
       :math:`n_1` and :math:`n_2` resp. the length of *t1* and *t2*

    >>> import numpy
    >>> def cmp (x,y): 
    ...    if x == y:
    ...       return 0
    ...    elif x < y:
    ...       return -1
    ...    else:
    ...       return 1
    >>> t1 = numpy.array([0,2,5,6])
    >>> t2 = numpy.array([1,3,4])
    >>> merge(t1,t2,cmp)
    array([0, 1, 2, 3, 4, 5, 6])
    """
    n1 = len(t1)
    n2 = len(t2)
    t = numpy.empty(n1+n2,dtype=type(t1[0]))
    i = j = k = 0
    while i < n1 and j < n2:
        if cmp(t1[i],t2[j]) < 0:
            t[k] = t1[i]
            i = i + 1
        else:
            t[k] = t2[j]
            j = j + 1
        k = k + 1
    while i < n1:
        t[k] = t1[i]
        i = i + 1
        k = k + 1
    while j < n2:
        t[k] = t2[j]
        j = j + 1
        k = k + 1
    return t

def merge_sort (t,cmp):
    """
    A sorting function implementing the merge sort algorithm
    
    :param t: A array of integers
    :type t: array
    :param cmp: A comparison function, returning 0 if a == b, -1 is a < b, 1 if a > b
    :type cmp: function
    :return: A fresh array, sorted.
    :rtype: array

    .. note::
    
       time complexity of merge is :math:`O(n_1+n_2)` with
       :math:`n_1` and :math:`n_2` resp. the length of *t1* and *t2*

    >>> import marker
    >>> def cmp (x,y): 
    ...    return x.cmp(y)
    >>> t = numpy.array(marker.Marker.markers(10))
    >>> merge_sort(t,cmp)
    array([m0, m1, m2, m3, m4, m5, m6, m7, m8, m9], dtype=object)
    """
    n = len(t)
    if n <= 1:
        # cas de base
        return copy.deepcopy(t)
    else:
        # cas general
        t1 = merge_sort((t[0:((n-1)//2+1)]),cmp)
        t2 = merge_sort((t[((n-1)//2+1):n]),cmp)
        return merge(t1,t2,cmp)
    
if __name__ == "__main__":
    import doctest
    doctest.testmod()
    import marker
    import test
    t = marker.Marker.markers(100)
    print(t)
    print(merge_sort(t,test.compare))

# -*- coding: utf-8 -*-

"""
:mod:`sorting` module : sorting functions module for experience assignment

:author: `Dpt Informatique - FST - Univ. Lille <http://portail.fil.univ-lille1.fr>`

:date: 2018, january
"""

import copy
import numpy

def merge (t1,t2, cmp):
    """
    Given two sorted array, creates a fresh sorted array.
    
    :param t1: An array of objects
    :type t1: Array
    :param t2: An array of objects
    :type t1: Array
    :param cmp: A comparison function, returning 0 if a == b, -1 is a < b, 1 if a > b
    :type cmp: function
    :return: A fresh array, sorted.
    :rtype: array
    
    .. note::
    
       time complexity of merge is :math:`O(n_1+n_2)` with
       :math:`n_1` and :math:`n_2` resp. the length of *t1* and *t2*

    >>> import numpy
    >>> def cmp (x,y): 
    ...    if x == y:
    ...       return 0
    ...    elif x < y:
    ...       return -1
    ...    else:
    ...       return 1
    >>> t1 = numpy.array([0,2,5,6])
    >>> t2 = numpy.array([1,3,4])
    >>> merge(t1,t2,cmp)
    array([0, 1, 2, 3, 4, 5, 6])
    """
    n1 = len(t1)
    n2 = len(t2)
    t = numpy.empty(n1+n2,dtype=type(t1[0]))
    i = j = k = 0
    while i < n1 and j < n2:
        if cmp(t1[i],t2[j]) < 0:
            t[k] = t1[i]
            i = i + 1
        else:
            t[k] = t2[j]
            j = j + 1
        k = k + 1
    while i < n1:
        t[k] = t1[i]
        i = i + 1
        k = k + 1
    while j < n2:
        t[k] = t2[j]
        j = j + 1
        k = k + 1
    return t

def merge_sort (t,cmp):
    """
    A sorting function implementing the merge sort algorithm
    
    :param t: A array of integers
    :type t: array
    :param cmp: A comparison function, returning 0 if a == b, -1 is a < b, 1 if a > b
    :type cmp: function
    :return: A fresh array, sorted.
    :rtype: array

    .. note::
    
       time complexity of merge is :math:`O(n_1+n_2)` with
       :math:`n_1` and :math:`n_2` resp. the length of *t1* and *t2*

    >>> import marker
    >>> def cmp (x,y): 
    ...    return x.cmp(y)
    >>> t = numpy.array(marker.Marker.markers(10))
    >>> merge_sort(t,cmp)
    array([m0, m1, m2, m3, m4, m5, m6, m7, m8, m9], dtype=object)
    """
    n = len(t)
    if n <= 1:
        # cas de base
        return copy.deepcopy(t)
    else:
        # cas general
        t1 = merge_sort((t[0:((n-1)//2+1)]),cmp)
        t2 = merge_sort((t[((n-1)//2+1):n]),cmp)
        return merge(t1,t2,cmp)
    
if __name__ == "__main__":
    import doctest
    doctest.testmod()
    import marker
    import test
    t = marker.Marker.markers(100)
    print(t)
    print(merge_sort(t,test.compare))

# -*- coding: utf-8 -*- :mod:`sorting` module : sorting functions module for experience assignment  :author: `Dpt Informatique - FST - Univ. Lille <http://portail.fil.univ-lille1.fr>`  :date: 2018, january Given two sorted array, creates a fresh sorted array.          :param t1: An array of objects     :type t1: Array     :param t2: An array of objects     :type t1: Array     :param cmp: A comparison function, returning 0 if a == b, -1 is a < b, 1 if a > b     :type cmp: function     :return: A fresh array, sorted.     :rtype: array          .. note::             time complexity of merge is :math:`O(n_1+n_2)` with        :math:`n_1` and :math:`n_2` resp. the length of *t1* and *t2*      >>> import numpy     >>> def cmp (x,y):      ...    if x == y:     ...       return 0     ...    elif x < y:     ...       return -1     ...    else:     ...       return 1     >>> t1 = numpy.array([0,2,5,6])     >>> t2 = numpy.array([1,3,4])     >>> merge(t1,t2,cmp)     array([0, 1, 2, 3, 4, 5, 6]) A sorting function implementing the merge sort algorithm          :param t: A array of integers     :type t: array     :param cmp: A comparison function, returning 0 if a == b, -1 is a < b, 1 if a > b     :type cmp: function     :return: A fresh array, sorted.     :rtype: array      .. note::             time complexity of merge is :math:`O(n_1+n_2)` with        :math:`n_1` and :math:`n_2` resp. the length of *t1* and *t2*      >>> import marker     >>> def cmp (x,y):      ...    return x.cmp(y)     >>> t = numpy.array(marker.Marker.markers(10))     >>> merge_sort(t,cmp)     array([m0, m1, m2, m3, m4, m5, m6, m7, m8, m9], dtype=object) # cas de base # cas general