[સંગીત વગાડવાનો] 

ડો LLOYD: ઠીક છે, તેથી એક મર્જ સૉર્ટ હજુ સુધી અન્ય અલ્ગોરિધમનો છે અમે બહાર સૉર્ટ કરવા માટે ઉપયોગ કરી શકો છો એક એરે તત્વો છે. અમે જોશો છે પરંતુ, તે મળ્યું છે ખૂબ જ મૂળભૂત તફાવત પસંદગી સૉર્ટ કરો, બબલ થી સૉર્ટ કરો, અને નિવેશ સૉર્ટ તે ખરેખર ખૂબ હોંશિયાર બનાવે છે. 

મર્જ પાછળનો મૂળ ખ્યાલ સૉર્ટ નાના એરે સૉર્ટ કરો અને પછી તે એરે ભેગા તેની સાથે, અથવા them-- મર્જ તેથી ક્રમમાં આ name--. સૉર્ટ કરે મર્જ કે જે રીતે આ એક સાધન ઉચ્ચાલન છે શું છે, કે જે રિકર્ઝન કહેવાય અમે ટૂંક સમયમાં વિશે વાત કરી રહ્યા છીએ પરંતુ અમે ખરેખર હજુ સુધી વિશે વાત કરી છે. 

અહીં મર્જ સૉર્ટ પાછળનો મૂળ વિચાર છે. એરે ડાબી અડધા સૉર્ટ એ એમ ધારી રહ્યા છીએ 1 કરતા વધારે છે. અને હું જ્યારે હું કહી શું અર્થ એ એમ ધારી રહ્યા છીએ, 1 કરતાં પણ મહાન છે હું અમે સંમત કરી શકો છો લાગે છે કે એક એરે તો માત્ર એક જ તત્વ સમાવેશ થાય છે, તે છટણી છે. અમે ખરેખર જરૂર નથી તે કંઈ પણ કરવા માટે. અમે હમણાં જ તે અલગ કરવામાં આવે છે જાહેર કરી શકે છે. તે માત્ર એક જ તત્વ છે. 

તેથી સ્યુડોકોડનો, ફરી, છે એરે ડાબી અડધા સૉર્ટ પછી જમણી અડધા એરે સૉર્ટ, પછી એકસાથે બે છિદ્ર મર્જ. હવે, પહેલેથી જ તમે હોઈ શકે છે વિચારવાનો, તે પ્રકારની માત્ર the-- તમે બંધ આપી રહ્યા છીએ જેવી લાગે તમે ખરેખર કંઇ કરવાનું નથી. તમે ડાબી સૉર્ટ કહી રહ્યાં છે અડધા જમણી અડધા સૉર્ટ પરંતુ તમે કહેવાની કરી રહ્યાં છો મને તમે તેને કેવી રીતે કરી રહ્યા છીએ. 

પરંતુ લાંબા સમય સુધી તરીકે યાદ રાખો કે ઝાકઝમાળ એક તત્વ છે, અમે તે છટણી જાહેર કરી શકે છે. પછી અમે માત્ર તેમને એકસાથે ભેગા કરી શકો છો. અને તે ખરેખર છે મર્જ સૉર્ટ પાછળ મૂળભૂત વિચાર, કે જેથી તે તોડી છે તમારા એરે કદ એક છે. અને પછી તમે ત્યાંથી પુનઃબીલ્ડ. 

સૉર્ટ ચોક્કસપણે છે મર્જ એક જટિલ અલ્ગોરિધમનો. અને તે પણ થોડી છે વિઝ્યુઅલાઈઝ જટિલ. તેથી આશા છે કે, આ દ્રશ્ય કે હું તમે અનુસરવા માટે મદદ કરશે અહીં છે. અને હું વસ્તુઓ વર્ણવવું કરવા માટે મારા શ્રેષ્ઠ પ્રયાસ કરીશું અને આ એક થોડી વધુ દ્વારા આગળ વધો ધીમે ધીમે અન્ય લોકો કરતાં માત્ર આસ્થાપૂર્વક તમારા માથા વિચાર મર્જ સૉર્ટ પાછળ વિચારો આસપાસ. 

તેથી અમે તરીકે જ એરે હોય છે અન્ય સૉર્ટ અલ્ગોરિધમનો વિડિઓઝ તમે જોઇ છે, તો them-- છ તત્વ એરે. અને અહીં અમારા સ્યુડોકોડનો કોડ જેવું છે ડાબી અડધા જમણી અડધા સૉર્ટ એકસાથે બે છિદ્ર મર્જ. તેથી આપણે આ ખૂબ જ કાળી ઈંટ લાલ લેવા દો એરે અને તે ડાબી અડધા સૉર્ટ. 

તેટલા સમય માટે તેથી, અમે જઈ રહ્યાં છો જમણી બાજુ પર સામગ્રી અવગણવા. તે ત્યાં છે, પરંતુ અમે છો હજુ સુધી તે પગલું છે. અમે છો નથી સૉર્ટ એરે જમણી અડધા. અમે સૉર્ટ ડાબી પર છો એરે અડધા. અને માત્ર ખાતર થોડી વધુ હોવા સ્પષ્ટ છે, તેથી હું ઉલ્લેખ કરી શકે છે શું પગલું અમે પર છો, હું સ્વિચ કરવા માટે જઈ રહ્યો છું નારંગી આ સમૂહ રંગ. હવે, અમે હજુ પણ વિશે વાત કરી રહ્યાં છો મૂળ એરે જ ડાબી અડધા. પરંતુ હું કરવા સક્ષમ હોવા દ્વારા કે આશા છું વિવિધ વસ્તુઓ ના રંગો નો સંદર્ભ લો તે થોડી વધુ બનાવવા પડશે અહીં શું થઈ રહ્યું છે સાફ કરો. 

ઠીક છે, તેથી હવે અમે હોય ત્રણ તત્વ એરે. અમે આ ડાબી અડધા સૉર્ટ કરો છો કેવી રીતે હજુ પણ આ પગલું છે, જે એરે? અમે ડાબી સૉર્ટ કરવાનો પ્રયાસ કરી રહ્યાં છો, ઈંટ લાલ એરે અડધા ડાબી અડધા જે હવે હું નારંગી રંગના છે. 

વેલ, અમે પ્રયાસ કરી શકે ફરીથી આ પ્રક્રિયા પુનરાવર્તન કરો. તેથી અમે હજી પણ સૉર્ટ કરવાનો પ્રયાસ મધ્ય સંપૂર્ણ એરે ડાબી અડધા. આ ડાબી અડધા અરે, હું હમણાં જ જાઉં છું આપખુદ નક્કી કરવા માટે તે ડાબી અડધા જમણી અડધા કરતાં નાની હશે, આ માટે થાય છે, કારણ કે ત્રણ તત્વો સમાવેશ થાય છે. 

અને તેથી હું કે કહેવું જાઉં છું ડાબી અડધા એરે ડાબી અડધા માત્ર તત્વ પાંચ છે. પાંચ, એક તત્વ છે અરે, અમે તેને સૉર્ટ કરવા માટે કેવી રીતે ખબર. અને તેથી પાંચ છટણી કરવામાં આવે છે. અમે હમણાં જ જાહેર કરવા જઈ રહ્યાં છો. તે એક તત્વ એરે છે. 

તેથી અમે હવે સૉર્ટ કરેલા ડાબી half-- ડાબી અડધા અથવા બદલે, અમે સૉર્ટ કરેલા નારંગી ડાબી અડધા. તેથી હવે, ક્રમમાં હજુ પણ સંપૂર્ણ એકંદર એરે ડાબી અડધા અમે અધિકાર અડધા સૉર્ટ જરૂર નારંગી, અથવા આ સામગ્રી. અમે તે કેવી રીતે કરવું? વેલ, અમે એક બે તત્વ એરે હોય છે. તેથી અમે ડાબી અડધા સૉર્ટ કરી શકો છો બે છે, જે એરે છે. બે એક તત્વ છે. તેથી તે મૂળભૂત રીતે છટણી છે. પછી અમે અધિકાર અડધા સૉર્ટ કરી શકો છો એરે, એક ભાગનું. તે મૂળભૂત દ્વારા સૉર્ટ કરો છે. 

આ હવે પ્રથમ સમય છે અમે મર્જ પગલું પહોંચી ગયા છો. અમે તેમ છતાં, પૂર્ણ કર્યા આપણે હવે પ્રકારની down-- નેસ્ટ રહ્યાં છો અને તે મુશ્કેલ જેવું છે રિકર્ઝન સાથે વસ્તુ છે, તમે તમારા રાખવા જરૂર જ્યાં અમે છે વિશે વડા. તેથી અમે ડાબી સૉર્ટ કરેલા નારંગી ભાગ અડધા. 

અને હવે, અમે સૉર્ટ મધ્યમાં છો નારંગી ભાગ જમણી અડધા. અને તે પ્રક્રિયા, અમે છે પગલું પર હોય હવે, એકસાથે બે છિદ્ર મર્જ. અમે બે છિદ્ર જોવા એરે, અમે બે અને એક જુઓ. જે તત્વ નાની હોય છે? એક. 

પછી જે તત્વ નાની હોય છે? વેલ, તે બે અથવા કશું જ નથી. તેથી તે બે છે. તેથી હવે, માત્ર ફરીથી ફ્રેમની અમે સંદર્ભમાં છે, જ્યાં અમે અલગ છે નારંગી ડાબી અડધા અને મૂળ જમણી અડધા. હું રંગો બદલાઈ છે ખબર જ્યાં અમે હતા ફરી, પરંતુ તે છે. અને કારણ હું આ કર્યું આ પ્રક્રિયા છે, કારણ કે છે નીચે વારો, ચાલુ રાખવા માટે જઈ રહી છે. અમે ડાબી છટણી કરી ભૂતપૂર્વ નારંગી અડધા અને ભૂતપૂર્વ નારંગી જમણી અડધા. 

હવે, આપણે તે મર્જ કરવાની જરૂર છે સાથે મળીને પણ બે છિદ્ર. એટલે કે, અમે પર છો પગલું છે. તેથી અમે તમામ ધ્યાનમાં હવે લીલા છે કે તત્વો, મૂળ એરે ડાબી અડધા. અને અમે તે મર્જ આ જ પ્રક્રિયા નો ઉપયોગ કરીને અમે બે મર્જ માટે કર્યું અને એક માત્ર એક ક્ષણ પહેલા. 

ડાબી અડધા નાના ડાબી અડધા ભાગ પર તત્વ પાંચ છે. નાના તત્વ પર જમણી અડધા છે. તે જે નાના છે? એક. 

નાના તત્વ પર ડાબી અડધા પાંચ છે. નાના તત્વ પર જમણી અડધા બે છે. નાના શું છે? બે. અને પછી છેલ્લે પાંચ અને કંઇ, અમે પાંચ કહી શકો છો. 

ઠીક છે, તેથી મોટા ચિત્ર, ચાલો એક બીજા માટે વિરામ લે છે જ્યાં અમે છે અને બહાર આકૃતિ. અમે શરૂ, તો ખૂબ જ શરૂઆત, અમે હવે પૂર્ણ કર્યા એકંદર એરે માત્ર અહીં સ્યુડોકોડનો કોડ એક પગલું. અમે અલગ છે એરે ડાબી અડધા. 

મૂળ કે યાદ ક્રમમાં પાંચ, બે, એક હતો. આ પ્રક્રિયા મારફતે જઈને અને નીચે માળો અને પુનરાવર્તન સમસ્યા તોડી ચાલુ નીચે નાના અને નાના ભાગોમાં, આપણે હવે પૂર્ણ કર્યા સ્યુડોકોડનો એક પગલું સમગ્ર શરૂ એરે માટે. અમે તેના ડાબી અડધા સૉર્ટ છે. 

તેથી હવે આપણે ત્યાં સ્થિર દો. અને હવે આપણે જમણી પ્રકાર દો મૂળ એરે અડધા. અને અમે દ્વારા તે કરવા માટે જઈ રહ્યાં છો એ જ પુનરાવર્તન પસાર થઇ વસ્તુઓ તોડી પ્રક્રિયા અને પછી તેમને એકસાથે મર્જ. 

તેથી ડાબી અડધા લાલ, અથવા ડાબી અડધા મૂળ જમણી અડધા અરે, હું કહેવા જાઉં છું ત્રણ છે. ફરીથી, હું અહીં સતત બની રહ્યો છું. તમે એક વિચિત્ર હોય, તો તત્વો સંખ્યા છે, તે ખરેખર છે કે કેમ તે તો કોઈ વાંધો નથી તમે ડાબી એક નાના બનાવવા અથવા જમણી એક નાના. 

શું બાબતો છે જ્યારે તમે તે કરવા આ સમસ્યા ઊભી થાય એક મર્જ, તમે સતત પ્રયત્ન કરવાની જરૂર છે. તમે ક્યાં તો હંમેશા જરૂર એક ડાબી બાજુ નાના બનાવવા અથવા હંમેશા કરવાની જરૂર છે જમણી બાજુ નાના. અહીં, હું હંમેશા કરવા માટે પસંદ કર્યા ડાબી બાજુ નાના બનાવવા ત્યારે મારા એરે, અથવા મારા પેટા એરે એક વિચિત્ર કદ છે. 

ત્રણ એક તત્વ છે, અને તેથી તે છટણી કરવામાં આવે છે. અમે તે ધારણા લિવરેજ કર્યું અમારા સમગ્ર પ્રક્રિયા દરમ્યાન અત્યાર સુધી. તેથી હવે આપણે જમણી પ્રકાર દો જમણી અડધા અડધા, અથવા Red જમણી અડધા. 

ફરીથી, અમે આ નીચે વિભાજિત કરવાની જરૂર છે. આ એક તત્વ એરે નથી. અમે તે છટણી જાહેર કરી શકતા નથી. અને તેથી પ્રથમ, અમે જઈ રહ્યાં છો ડાબી અડધા સૉર્ટ. 

ડાબી અડધા એક તત્વ છે, તેથી તે મૂળભૂત રીતે પ્રકારની છે. પછી અમે અધિકાર સૉર્ટ જઈ રહ્યાં છો એક તત્વ છે, જે અડધા. તે મૂળભૂત રીતે છટણી છે. અને હવે, અમે સાથે તે બે મર્જ કરી શકો છો. ચાર નાના છે, અને પછી છ નાની હોય છે. 

ફરીથી, અમે શું આ બિંદુએ કર્યું છે? અમે ડાબી છટણી કરી જમણી અડધા અડધા. અથવા મૂળ પર પાછા જવાનું ત્યાં હતા કે રંગો, અમે ડાબી છટણી કરી નરમ લાલ અડધા. તે અસલમાં એક ઘેરી ઈંટ હતી લાલ અને હવે તે એક નરમ લાલ છે, અથવા તે નરમ લાલ હતી. 

અને પછી અમે સૉર્ટ કરેલા નરમ લાલ જમણી અડધા. હવે, સાથે સાથે, તેઓ માત્ર ફરીથી લીલા છો અમે એક પ્રક્રિયા પસાર થઇ રહ્યાં છો કારણ કે. અને અમે પુનરાવર્તન છે આ ઉપર અને ઉપર. 

તેથી હવે અમે તે મર્જ કરી શકો છો એકસાથે બે છિદ્ર. અને તે અમે અહીં શું છે. આ કાળી લીટી તેથી માત્ર ડાબી અડધા વિભાજિત અને આ પ્રકારની ભાગ જમણી અડધા. 

અમે નાના કિંમત એરે ડાબી બાજુ પર અથવા મને માફ, નાના ડાબી અડધા કિંમત અધિકાર નાના કિંમત અડધા અને ત્રણ નાની હોય છે કે જે શોધી. અને હવે એક ઓપ્ટિમાઇઝેશન એક બીટ, અધિકાર? કંઇ ખરેખર છે ડાબી બાજુ પર છોડી. 

બાકી કશું જ નથી ડાબી બાજુ પર, જેથી અમે અસરકારક રીતે કરી શકો છો માત્ર અમે જાહેર કરી શકે છે move-- તે બાકીના ખરેખર છે છટણી અને માત્ર તે ખીલી કશું જ નથી કારણ કે, પર સામે સરખાવવા માટે બીજું. અને આપણે જાણીએ છીએ જમણી બાજુ કે જમણી બાજુ છટણી કરવામાં આવે છે. 

ઠીક છે, તેથી હવે આપણે ફરી સ્થિર દો અને અમે વાર્તા છે, જ્યાં બહાર આકૃતિ. એકંદર એરે, અમે શું પરિપૂર્ણ છે? અમે ખરેખર પરિપૂર્ણ કર્યું હવે એક અને બે પગલું જાય છે. અમે ડાબી અડધા સૉર્ટ કરો, અને અમે અધિકાર અડધા ઉકેલ. 

તેથી હવે, રહે છે બધા અમને માટે છે સાથે તે બે છિદ્ર મર્જ કરવા. તેથી અમે સૌથી નીચો મૂલ્ય તુલના એરે દરેક અડધા તત્વ અને બદલામાં આગળ ધપાવો. ત્રણ કરતાં ઓછી છે, તેથી એક જાય છે. 

બે ત્રણ કરતાં ઓછી છે, તેથી બે જાય છે. ત્રણ 5 કરતાં ઓછી છે, તેથી ત્રણ જાય છે. ચાર 5 કરતાં ઓછી હોય છે, તેથી ચાર જાય છે. પછી પાંચ, છ કરતાં ઓછી છે અને છ બધા કે જે રહે છે. 

હવે મને ખબર છે, કે જે પગલાં ઘણો હતો. અને અમે ઘણો છોડી દીધું છે અમારા પગલે મેમરી. અને તે તે ગ્રે ચોરસ શું હોય છે. કે લીધો એવું અને તે કદાચ લાગ્યું નિવેશ સૉર્ટ કરતાં લાંબા સમય સુધી ઘણો બબલ સૉર્ટ કરો, અથવા પસંદ સૉર્ટ કરો. 

પરંતુ, વાસ્તવમાં, કારણ કે આ પ્રક્રિયા ઘણો એ જ time-- પર રહ્યું છે જે ફરી, અમે કરશો કંઈક છે અમે વિશે વાત ત્યારે વિશે વાત ભવિષ્યમાં પુનરાવર્તન વિડીયો ખરેખર આ અલ્ગોરિધમનો સ્પષ્ટ મૂળભૂત છે કંઈપણ કરતાં અલગ અમે પહેલાં જોઈ હોય પરંતુ નોંધપાત્ર છે વધુ કાર્યક્ષમ. 

શા માટે છે? વેલ, સૌથી ખરાબ કેસ દૃશ્ય, અમે છે n તત્વોના અપ વિભાજિત અને પછી તેમને ફરીથી. પરંતુ અમે ફરીથી જ્યારે તેમને અમે શું કરી રહ્યા છીએ મૂળભૂત બમણી છે નાના એરે માપ. અમે એક તત્વ એક ટોળું હોય છે એરે કે અમે અસરકારક રીતે બે તત્વ એરે માં ભેગા કરો. અને પછી અમે તે લેવા બે તત્વ એરે અને માં તેમને એકસાથે ભેગા તેથી ચાર તત્વ એરે, અને, અને તેથી પર, અને તેથી પર, અમે ત્યાં સુધી એક એ તત્વ એરે હોય છે. 

પરંતુ કેટલા doublings તે n મેળવવા લાગી છે? પાછા ફોન પુસ્તક ઉદાહરણ વિચારો. કેટલી વખત આપણે અશ્રુ હોય અડધા ફોન પુસ્તક, કેટલા વધુ વખત આપણે ફોન બુકમાં અશ્રુ હોય અડધા, તો ફોન પુસ્તક કદ બમણો? માત્ર એક યોગ્ય, ત્યાં છે? 

તેથી અમુક પ્રકારના હોય છે અહીં લઘુગુણકીય તત્વ. પરંતુ અમે પણ હજુ પણ ઓછામાં ઓછા આ n તત્વોના બધા જુઓ. સૌથી ખરાબ કેસ દૃશ્ય તેથી સૉર્ટ n લોગ n ચાલે મર્જ. અમે જોવા માટે હોય છે એન બધા તત્વો, અને અમે તેમને ભેગા છે સાથે મળીને લોગ n પગલાંઓ સેટમાં. શ્રેષ્ઠ કેસ દૃશ્ય માં, એરે સંપૂર્ણપણે છટણી કરવામાં આવે છે. તે મહાન છે. પરંતુ એલ્ગોરીધમ પર આધારીત અમે અહીં છે અમે હજુ પણ વિભાજિત અને ફરીથી કરવા માટે હોય છે. આ કિસ્સામાં, તેમ છતાં, recombining બિનઅસરકારક પ્રકારની છે. તે જરૂરી નથી. પરંતુ અમે હજુ પણ મારફતે જાઓ કોઈપણ રીતે સમગ્ર પ્રક્રિયા. 

શ્રેષ્ઠ કિસ્સામાં તેથી અને સૌથી ખરાબ કિસ્સામાં, આ અલ્ગોરિધમનો n લોગ n એ સમય ચાલે છે. મર્જ કરો સૉર્ટ ચોક્કસપણે એક બીટ trickier છે અન્ય મુખ્ય સોર્ટિંગ એલ્ગોરિધમ્સ કરતાં અમે CS50 વિશે વાત કરી છે, પરંતુ કર્યું નોંધપાત્ર વધુ શક્તિશાળી. 

અને તેથી જો તમે ક્યારેય શોધવા પ્રસંગે તે જરૂર અથવા સૉર્ટ તેનો ઉપયોગ કરવા માટે મોટા ડેટા સેટ મેળવવામાં પુનરાવર્તનના વિચાર આસપાસ તમારા માથા ખરેખર શક્તિશાળી બની રહ્યું છે. અને તે બનાવવા માટે ચાલી રહ્યું છે તમારા કાર્યક્રમો ખરેખર વધુ કાર્યક્ષમ અન્ય કંઈપણ વિરુદ્ધ સૉર્ટ મર્જ મદદથી. હું ડો લોયડ છું. આ CS50 છે.