O(nlogn) recursive Merge Sort accepted


  • 1
    C

    I know it breaks the requirement of constant space, but my quick sort keeps time out on the bad cases.


  • 3
    M

    Leetcode cannot detect how much memory you are using, so while it asks for constant space, so long as it isn't immensely overinflated, you can use memory in your algorithm and it will accept it. Like you said, though, that breaks the requirements of the problem. However, there is a way to do merge sort without using recursion, which allows you to use it in constant space. Try looking at a "bottom-up" merge sort, and see how you could adapt it to linked lists.

    On a slight side note, do remember that quick sort has a worst case time complexity of O(n^2), which could be failing you if your pivot is not chosen well for the array.


  • 0
    B

    Merge Sorting a vector need O(n) space. However, Merge Sorting a link list need O(1) space. The time complexity for them are both O(n logn)


  • 0
    A

    I am getting TLE for merge sort for large input size. Wondering on why is it so. Logically every one's merge sort will be almost same.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.