/sorts/merge_sort_fastest.py is NOT fast at all

[tom5610]

Hi @harshildarji & @yesIamHasi ,

Thanks for sharing algorithm source code and I really like them.

Just want to raise an issue on '/sorts/merge_sort_fastest.py' that it is not an merge_sort option as there are dependencies on python built-in functions - remove(), max() & min(), which makes 'merge_sort_fastest' like O(n^2) [ (n*(n+1)) / 2 * 2 as one max()/min() with remove()] instead of O(n log n).

For example, while sorting 50,000 random numbers with below list:
unsorted = random.sample(range(0, 100000), 50000)

The running result will be like:
(venv) $ time python3 merge_sort.py
real 0m0.361s
user 0m0.347s
sys 0m0.011s

(venv) $ time python3 merge_sort_fastest.py
real 0m49.306s
user 0m49.103s
sys 0m0.099s

thanks!
Tom

[sumitkumar22299]

Yes! @tom5610 you are right. The usage of inbuilt functions is not right here to make program faster.
By the way the Python/sorts/merge_sort.py is more faster than this.

[crazymerlyn]

It's also not merge sort. It's some weird two-pronged version of selection sort.

[pandyamarut]

# Merges two subarrays of arr[]. 
# First subarray is arr[l..m] 
# Second subarray is arr[m+1..r] 
def merge(arr, l, m, r): 
    n1 = m - l + 1
    n2 = r- m 
  
    # create temp arrays 
    L = [0] * (n1) 
    R = [0] * (n2) 
  
    # Copy data to temp arrays L[] and R[] 
    for i in range(0 , n1): 
        L[i] = arr[l + i] 
  
    for j in range(0 , n2): 
        R[j] = arr[m + 1 + j] 
  
    # Merge the temp arrays back into arr[l..r] 
    i = 0     # Initial index of first subarray 
    j = 0     # Initial index of second subarray 
    k = l     # Initial index of merged subarray 
  
    while i < n1 and j < n2 : 
        if L[i] <= R[j]: 
            arr[k] = L[i] 
            i += 1
        else: 
            arr[k] = R[j] 
            j += 1
        k += 1
  
    # Copy the remaining elements of L[], if there 
    # are any 
    while i < n1: 
        arr[k] = L[i] 
        i += 1
        k += 1
  
    # Copy the remaining elements of R[], if there 
    # are any 
    while j < n2: 
        arr[k] = R[j] 
        j += 1
        k += 1
  
# l is for left index and r is right index of the 
# sub-array of arr to be sorted 
def mergeSort(arr,l,r): 
    if l < r: 
  
        # Same as (l+r)/2, but avoids overflow for 
        # large l and h 
        m = (l+(r-1))/2
  
        # Sort first and second halves 
        mergeSort(arr, l, m) 
        mergeSort(arr, m+1, r) 
        merge(arr, l, m, r) 

PLEASE CHECK THIS. i HOPE IT HELPS

[brunohadlich]

I think we could rename merge_sort_fastest.py to something else as it is not fast at all neither resembles merge sort. What do you think?

[bardia52]

@brunohadlich ,
I think we should have only one merge_sort file not merge_sort.py and merge_sort_fastest.py. I will inspect these two files and get back to you. What do you think?

[brunohadlich]

I agree, it's been a long time since my last contribution to this project as I'm busy with other tasks. Feel free to discuss and apply the best solution.

[bardia52]

It's ok, I just started on this project. I will spend more time on it and keep it posted here.

[bardia52]

Hi @brunohadlich
I looked at these two files:

• merge_sort.py
• merge_sort_fastest.py

The one that I recommend to keep is merge_sort.py, the other one is NOT merge sort algorithm. It's something else that works fine but for the sake of algorithm education is misleading.

Let me know if there is any more work to be done on this issue, otherwise after deleting the file 'merge_sort_fastest.py' we can close this issue.

Note: @cclauss please look at this message.

[onlinejudge95]

Just raise a PR for the same

[cclauss]

Please open a PR that renames merge_sort_fastest.py to unknown_sort.py.

[bardia52]

OK sure, thank you.

[bardia52]

PR is created: #1612.