Results 1 to 11 of 11
  1. #1
    nbd223 is offline Member
    Join Date
    Apr 2008
    Location
    Boston
    Posts
    3
    Rep Power
    0

    Default Quick question about sorting

    Hi first off i would like to thank everyone who is taking time to help out the people posing questions on this forum.

    I was wondering however in the best case scenario which is fast a merge sort (i belive it is n lg n) or and insertion sort ( n)?

    Also what is the big o notation for merging 2 already sorted arrays?

    Thank you for your time.

  2. #2
    Zosden's Avatar
    Zosden is offline Senior Member
    Join Date
    Apr 2008
    Posts
    384
    Rep Power
    6

    Default

    merge sort is faster, but takes up more space, which usually isn't an issue. Are you by any chance in discrete mathematics or something similar
    My IP address is 127.0.0.1

  3. #3
    Eranga's Avatar
    Eranga is offline Moderator
    Join Date
    Jul 2007
    Location
    Colombo, Sri Lanka
    Posts
    11,372
    Blog Entries
    1
    Rep Power
    19

    Default

    Hi nbd223,

    Welcome to our community. :)

    Yes as Zosden says, merge sort is much faster. You can make two simple applications and test it pal.

  4. #4
    Zosden's Avatar
    Zosden is offline Senior Member
    Join Date
    Apr 2008
    Posts
    384
    Rep Power
    6

    Default

    I would personally use quick sort it is the best unless the array is already sorted.
    My IP address is 127.0.0.1

  5. #5
    nbd223 is offline Member
    Join Date
    Apr 2008
    Location
    Boston
    Posts
    3
    Rep Power
    0

    Default

    I actually am thankyou very much for your help. One more quick question what is the base case for a merge sort? Thanks for your help.

  6. #6
    Zosden's Avatar
    Zosden is offline Senior Member
    Join Date
    Apr 2008
    Posts
    384
    Rep Power
    6

    Default

    merge sort is always n lgn
    My IP address is 127.0.0.1

  7. #7
    Eranga's Avatar
    Eranga is offline Moderator
    Join Date
    Jul 2007
    Location
    Colombo, Sri Lanka
    Posts
    11,372
    Blog Entries
    1
    Rep Power
    19

  8. #8
    Zosden's Avatar
    Zosden is offline Senior Member
    Join Date
    Apr 2008
    Posts
    384
    Rep Power
    6

    Default

    unfortunately yes. Java = easy discrete = death by firing squad.
    My IP address is 127.0.0.1

  9. #9
    nbd223 is offline Member
    Join Date
    Apr 2008
    Location
    Boston
    Posts
    3
    Rep Power
    0

    Default

    Sorry one last question. What would the big o notation be for merging the finale 2 sorted arrays on the way back up in a merge sort?

  10. #10
    Zosden's Avatar
    Zosden is offline Senior Member
    Join Date
    Apr 2008
    Posts
    384
    Rep Power
    6

    Default

    i believe its n - 1 worse case n/2 best case
    My IP address is 127.0.0.1

  11. #11
    Eranga's Avatar
    Eranga is offline Moderator
    Join Date
    Jul 2007
    Location
    Colombo, Sri Lanka
    Posts
    11,372
    Blog Entries
    1
    Rep Power
    19

Similar Threads

  1. Quick Java question/help
    By Zedy in forum New To Java
    Replies: 6
    Last Post: 04-22-2008, 03:40 AM
  2. Quick Help Please! Can't Run Code!!
    By VinceGuad in forum Eclipse
    Replies: 4
    Last Post: 01-16-2008, 03:54 AM
  3. Quick Stupid Question
    By bluekswing in forum New To Java
    Replies: 7
    Last Post: 01-08-2008, 06:35 PM
  4. Quick Job required in Java
    By taxman in forum Jobs Offered
    Replies: 0
    Last Post: 01-02-2008, 11:46 AM
  5. Quick Question (Functions)
    By ibanez270dx in forum New To Java
    Replies: 2
    Last Post: 11-16-2007, 01:42 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •