Sorting algorithm

> Surely it would require a sort that calls itself

> recursively? I don't see how the naive bubble-sort

> algorithm (for example) could cause a stack overflow.

It could though. If the implementation were bad enough.

What I meant was that he hadn't given enough information. Sorry if I was unclear.

~Cheers

Adeodatusa at 2007-7-9 13:16:42 >

> Any recursive algorithm can, but any recursive

> algorithm can be coded iterativly (although this is

> sometimes messier).

>

> Your stack size (in a best case) would need to go up

> with the number of keys in a log2(n) manner, but for

> some sorts in worst-case you would need to go up

> linearly.

With log2(N) recursive calls, my JVM (-server, defaults otherwise, jRockit) can sort a list of length 29834420244454770673524974070440207622769782185291668028777587494552308436731820541803802986238238322287396261159954005711468267947797957208998067468206317038659200376468075708225795370750900723181809674003371004021796650998121558790550541582924992806646697093651118266799723536405663216439456567384206497137337876351494706297847152418457281439433496508284491282572451957281961360120921276965110139823382136939779928118678527935341186436428579520991420654139530321453756899098859338190024046646243743427499587696369344020711772862231202873818283032795543342104967031088928261606689637450121896097890706300658274467743487130642415816813972244202244310658220684925334149616204249182364860472594935780277771176947412432590927895065719441308304954162476268845841840810934925058267098151702333554469730361931483244854937623715190392785577046389842006857136916479656157280754494430430900919121834405058428016404499890322171820803146383483626884301205923499294726340289608514344242419889645401660304065900277244171734927602687479846985225534522354523565145523211813365785046754416579053243457930070969136961116442515739640372002857871587975878455788008547726250515405882495622894119962788767807152672812875436278908998935643657739730861835150261406460483166480249150422321334488446793060660532311941258877854313072714847198723607043550344625590070523650879800883283889214239528728551489372184721993186958866576039437422477099713002725128152572644272325091349143862946599778179523218690924800360830404249613804020703103267860269289087693135030449085703375783973394775833798021488044637696050249419424208994001731369460047990013720552067173067873194652503635538795616529530830546491920555024734503701244476660178146519954376602361291208590703635175680986480377158709049670376629779148784438332065628580946798676113515319245711925343322472130503050839485132221630883372250154954237949507181687052739256668501961028051925450823526378390199611165371263217762484242297812788828874774237966766410633555576845776200639524171473385447191371701918242791434023858231928430917443602004990269188490255351848936742536979601088650561024307477133367334951312589937733513509167886161763711149162962713665184745862278940404767408908897208429281997366650089516682880491601328588995113903962163877485118671294901643893360199064583229714769186750197358767187970458506944396919520492179252381939608708336126257988350911531059967274546866873674180208452132685542331137207319607320750683669281043535210592443788240632958572237345658253409658683613678714535804723313933034821184277533975748289089655252351873454374746352285194539763181340354985061930161685779224125348817376505482848188134663483549186307146271709693685868443592861299101279746403196877086946127249126800387649611359470680556780896784802288159099934823097074704862186678103346845189547124385691613374106360273730464095155767785067929208302229344974534146607447777200848419403796627079158547366044597177773600033626523365761183490272890528593183694691671161603987407494194005015583981459385932063492963649000791900409282818350341042134889373684072779646252415647372204398616525040938646077030755174170481597967383221967207339160352237327306393046712758226946945081562141759729706189829991214952323140647202444547927921136509779434256333782876191293529331960184894236032268010919144129401157585506589442887160883644129332403253452913868825465252805022059641859661598124263427848457301249373845513586458334247697934894773709775012036433368551813709178357663895268064693612079673359376226020007583737008489439437531194835600166006246392072210395081445349802164508920914757702697163031568885317055604373330951174507851005205771548012535351717624014449641100977775415542818298211031576708445724765453202214593535402889147965106201004532791172478886990029986860760280571722038775701420150834128018681206378652780967412079095104754493769277785373269153172502030703335939603914789028614889873426987189685574160010968055753395739744380395398200053307526846857714736616146419893836332150213887534435807866710551652383903531895996410782283837121019784660829154514235071096145300443672985218764065949782324030776611059982246223993738387434961898742620419812697200856780881666968344723907387154841979307249547268908362456679682172777593954284360365038526801513334479077877466021503874904530083123720376190836796206975000673276508200859664751047970336212869615226789835907425985001308379957269300815607768617172731669234176786572523101129574953933810459291014342626194998739458151976963589946902324530824104143830765005416401805861437023464819436557527857132215461547851967389564917629782814326182314619001609741038766123151679985166063214758755068278725754519416649335190923256038086940818342107213388211331232061800092230399809358424228826119487931373124768993745121079328106191389830389447953121682681190213181165159562693101103783594443769628343717005815605463829201811724123550678418947593897426956745634880513776132457410252376018415291382065599555052337516662002460963786331300485279604228621379073130512277880445808901293359292069166692277227111743544807571414914232968066305357812542660110156584598187128471750101291880362927734261378824162152419657868100633520908105819435812016472709745544999296669929922848002681232915157494339011197527190490465536390091318545632866991376347102053062756022798917811213253718188262025160682530011138897901365938980253049654146745224776173317891222430386579917297007525546515842551916014005853171893038429601479848696809895587373731025655995881015849479502239408687294363036799500865653428066736248277628439128801104940097921869918194184285473033591833367278909762763258167870690990395891199254296283258017149460668286669756853315528711308286255538844697058471635489101858614666187745881209090429945193988862463668459432671239730421650066981294631989274072862912619342364461792669532583202397107612642354047157267950267469788421033144338654664616033046840947382563758832532377983457479585225217083922625874935438575233347366836886499364420678582753792811521774589593102621319933112968562021903693515332709221976244266872180775556728011357342593850597767540336026380877903149995312927315469268302796580849314227280202581670669774760922688548082070850243457932808938535344242186886251935834838211305495743609522024659624519426752301449285441062840574068846371345756982627645123267176820361626195898436608204903942207915995759211007166401095401927025072636173339201401215290259272600047421176123403756364481633249875195859417576773793930341389871053331062538514598759414716597766711973075124867192615015060429770142454176323742530755623470435316438098381427607911796849696897737096426571675474117473780087898852395687141105097422373763642481633169537271468519622930627871670952065758491064496065158864377774638272641123486690677530386818090404411457907315691802960650921939523406575310219401455557997427510430453894300294833120949755742637418524415062017849563036095918190635029382118691176939682338097148530930290603711279481241626838233162102542917981351031335386868910484386458159417948554419595581539792149539976709923213036778852189189492520406833944816239240343599699044531703199516475256361294981707310337615379135219403829797513876411441144286724954325315702080188148919579940241761259345361072814274639505061111904377715946299813218807679999825503210932927449694961518248633416242174265450251526038665102661252918899978271503455546454334104235202517341075769740236994171160742821207566207226380928098398393012453233136847888172178687997960272239628936396148048542943500687745527481153320012577931416093100615056891945469800417210793682286913921266960805420490632727393123378836747423263205508344980149421647738718515993569923205271941300647720018106467606644084253461120448349618460777023775989006664155897709789892655144152690327319990151842231940546428080311218370270679121680332642408006455530506672873561977587298682915246894092058179643261333600407416873290025169115535829555442608982589225208739309156472634538312565674065586261000735428048835292861946650798900887202264113131509430386987681739124313428859077825092105958782020696502891271456843399765367632803490709371110856761618493684290388586343418012679517430322746359893148670553593703841298466660368220104537469917254247913187858771838179359893682441971211903872551507613710515443114936000029853103098195304184671247905723887604126179236662088722823373837176473012025252073139765596409613893523789249067036828196424743150845504400728649669930193659792319769221267456 without stack overflow due to recursive calls. Other stresses on the system notwithstanding...

Adeodatusa at 2007-7-9 13:16:42 >