[SPARK-2983] [PySpark] improve performance of sortByKey()
[SPARK-2983] [PySpark] improve performance of sortByKey()

1. skip partitionBy() when numOfPartition is 1
2. use bisect_left (O(lg(N))) instread of loop (O(N)) in
rangePartitioner

Author: Davies Liu <davies.liu@gmail.com>

Closes #1898 from davies/sort and squashes the following commits:

0a9608b [Davies Liu] Merge branch 'master' into sort
1cf9565 [Davies Liu] improve performance of sortByKey()

stanzhai/spark,hhbyyh/spark,darionyaphet/spark,haowu80s/spark,aosagie/spark,JerryLead/spark,hvanhovell/spark,yanboliang/spark,szhem/spark,nchammas/spark,nchammas/spark,wzhfy/spark,bravo-zhang/spark,metamx/spark,caneGuy/spark,nlalevee/spark,ueshin/apache-spark,ptkool/spark,pgandhi999/spark,kimoonkim/spark,sachintyagi22/spark,JerryLead/spark,sureshthalamati/spark,WindCanDie/spark,guoxiaolongzte/spark,ajaysaini725/spark,mike0sv/spark,SnappyDataInc/spark,patrick-nicholson/spark,nilsgrabbert/spark,kimoonkim/spark,zero323/spark,dhruve/spark,nilsgrabbert/spark,srowen/spark,rekhajoshm/spark,brad-kaiser/spark,JoshRosen/spark,xuanyuanking/spark,xflin/spark,poffuomo/spark,taroplus/spark,mdespriee/spark,kimoonkim/spark,actuaryzhang/spark,bOOm-X/spark,narahari92/spark,apache-spark-on-k8s/spark,apache/spark,Panos-Bletsos/spark-cost-model-optimizer,shubhamchopra/spark,highfei2011/spark,cin/spark,wangmiao1981/spark,mike0sv/spark,huang1900/spark,shaneknapp/spark,ioana-delaney/spark,holdenk/spark,shuangshuangwang/spark,debugger87/spark,jiangxb1987/spark,WeichenXu123/spark,szhem/spark,minixalpha/spark,brad-kaiser/spark,jianran/spark,janewangfb/spark,ueshin/apache-spark,shubhamchopra/spark,zhouyejoe/spark,gioenn/xSpark,ahnqirage/spark,saturday-shi/spark,shuangshuangwang/spark,aosagie/spark,adrian-ionescu/apache-spark,maropu/spark,aokolnychyi/spark,skonto/spark,sahilTakiar/spark,milliman/spark,janewangfb/spark,darionyaphet/spark,shaneknapp/spark,vinodkc/spark,apache/spark,aosagie/spark,tejasapatil/spark,bOOm-X/spark,minixalpha/spark,techaddict/spark,pgandhi999/spark,sachintyagi22/spark,mdespriee/spark,setjet/spark,mike0sv/spark,stanzhai/spark,bdrillard/spark,holdenk/spark,dongjoon-hyun/spark,bravo-zhang/spark,bravo-zhang/spark,cin/spark,debugger87/spark,mdespriee/spark,ddna1021/spark,mahak/spark,setjet/spark,sachintyagi22/spark,sachintyagi22/spark,JoshRosen/spark,mahak/spark,MLnick/spark,wzhfy/spark,mzl9039/spark,zero323/spark,kiszk/spark,taroplus/spark,saturday-shi/spark,wangyum/spark,ddna1021/spark,pgandhi999/spark,ddna1021/spark,sahilTakiar/spark,nchammas/spark,darionyaphet/spark,lxsmnv/spark,zzcclp/spark,ConeyLiu/spark,rekhajoshm/spark,zuotingbing/spark,xflin/spark,joseph-torres/spark,srowen/spark,gengliangwang/spark,andrewor14/iolap,shaneknapp/spark,cloud-fan/spark,ueshin/apache-spark,zero323/spark,sahilTakiar/spark,tengpeng/spark,pgandhi999/spark,wangyum/spark,facaiy/spark,someorz/spark,shubhamchopra/spark,patrick-nicholson/spark,rednaxelafx/apache-spark,setjet/spark,aosagie/spark,techaddict/spark,WindCanDie/spark,caneGuy/spark,kissmetrics/spark,publicRoman/spark,apache-spark-on-k8s/spark,nchammas/spark,pronix/spark,haowu80s/spark,SHASHANKB/spark,lxsmnv/spark,metamx/spark,highfei2011/spark,1haodian/spark,WeichenXu123/spark,Aegeaner/spark,holdenk/spark,publicRoman/spark,tejasapatil/spark,facaiy/spark,ibm-research-ireland/sparkoscope,nlalevee/spark,byakuinss/spark,WindCanDie/spark,SnappyDataInc/spark,ahnqirage/spark,mahak/spark,debugger87/spark,andrewor14/iolap,milliman/spark,1haodian/spark,chuckchen/spark,saturday-shi/spark,Aegeaner/spark,highfei2011/spark,stanzhai/spark,andrewor14/spark,zero323/spark,adrian-ionescu/apache-spark,JoshRosen/spark,HyukjinKwon/spark,JerryLead/spark,wzhfy/spark,debugger87/spark,stanzhai/spark,icexelloss/spark,narahari92/spark,SHASHANKB/spark,caneGuy/spark,ron8hu/spark,ConeyLiu/spark,aokolnychyi/spark,cloud-fan/spark,hhbyyh/spark,wzhfy/spark,hvanhovell/spark,eyalfa/spark,narahari92/spark,shubhamchopra/spark,gengliangwang/spark,stanzhai/spark,tejasapatil/spark,actuaryzhang/spark,adrian-ionescu/apache-spark,wangmiao1981/spark,joseph-torres/spark,nlalevee/spark,byakuinss/spark,vinodkc/spark,pgandhi999/spark,jlopezmalla/spark,gioenn/xSpark,skonto/spark,liutang123/spark,janewangfb/spark,ConeyLiu/spark,gioenn/xSpark,pgandhi999/spark,zuotingbing/spark,michalsenkyr/spark,rekhajoshm/spark,milliman/spark,skonto/spark,jiangxb1987/spark,hhbyyh/spark,dhruve/spark,kissmetrics/spark,sahilTakiar/spark,chuckchen/spark,spark-test/spark,esi-mineset/spark,caneGuy/spark,kiszk/spark,holdenk/spark,alunarbeach/spark,publicRoman/spark,liutang123/spark,xflin/spark,aray/spark,shaneknapp/spark,akopich/spark,loneknightpy/spark,saltstar/spark,akopich/spark,mahak/spark,map222/spark,loneknightpy/spark,hhbyyh/spark,kiszk/spark,rednaxelafx/apache-spark,saturday-shi/spark,aosagie/spark,jkbradley/spark,map222/spark,markhamstra/spark,kiszk/spark,milliman/spark,zzcclp/spark,jiangxb1987/spark,ptkool/spark,vinodkc/spark,byakuinss/spark,brad-kaiser/spark,yanboliang/spark,haowu80s/spark,ioana-delaney/spark,saturday-shi/spark,skonto/spark,cloud-fan/spark,debugger87/spark,Panos-Bletsos/spark-cost-model-optimizer,apache/spark,setjet/spark,andrewor14/iolap,guoxiaolongzte/spark,holdenk/spark,panfengfeng/spark,dbtsai/spark,rekhajoshm/spark,Panos-Bletsos/spark-cost-model-optimizer,sachintyagi22/spark,mzl9039/spark,Aegeaner/spark,techaddict/spark,stanzhai/spark,huang1900/spark,esi-mineset/spark,pgandhi999/spark,rikima/spark,stanzhai/spark,ioana-delaney/spark,actuaryzhang/spark,debugger87/spark,minixalpha/spark,aosagie/spark,ibm-research-ireland/sparkoscope,esi-mineset/spark,rednaxelafx/apache-spark,caneGuy/spark,maropu/spark,actuaryzhang/spark,zhouyejoe/spark,BryanCutler/spark,goldmedal/spark,highfei2011/spark,jrshust/spark,WeichenXu123/spark,witgo/spark,nchammas/spark,facaiy/spark,big-pegasus/spark,zero323/spark,mahak/spark,alunarbeach/spark,byakuinss/spark,WeichenXu123/spark,kevinyu98/spark,yanboliang/spark,pronix/spark,tengpeng/spark,markhamstra/spark,ajaysaini725/spark,ron8hu/spark,WindCanDie/spark,bOOm-X/spark,ericvandenbergfb/spark,HyukjinKwon/spark,spark-test/spark,bdrillard/spark,maropu/spark,jianran/spark,Aegeaner/spark,witgo/spark,metamx/spark,ueshin/apache-spark,skonto/spark,joseph-torres/spark,jkbradley/spark,chuckchen/spark,wangyum/spark,SHASHANKB/spark,map222/spark,mdespriee/spark,panfengfeng/spark,jlopezmalla/spark,srowen/spark,bdrillard/spark,tejasapatil/spark,adrian-ionescu/apache-spark,rezasafi/spark,BryanCutler/spark,jrshust/spark,UndeadBaneGitHub/spark,ibm-research-ireland/sparkoscope,bOOm-X/spark,gengliangwang/spark,apache-spark-on-k8s/spark,caneGuy/spark,kiszk/spark,tejasapatil/spark,goldmedal/spark,kiszk/spark,guoxiaolongzte/spark,jlopezmalla/spark,facaiy/spark,joseph-torres/spark,dongjoon-hyun/spark,mdespriee/spark,nchammas/spark,rednaxelafx/apache-spark,rezasafi/spark,UndeadBaneGitHub/spark,zhouyejoe/spark,ConeyLiu/spark,BryanCutler/spark,hhbyyh/spark,rekhajoshm/spark,huang1900/spark,loneknightpy/spark,ueshin/apache-spark,liyichao/spark,mike0sv/spark,caneGuy/spark,liyichao/spark,byakuinss/spark,wzhfy/spark,ajaysaini725/spark,sahilTakiar/spark,jlopezmalla/spark,cin/spark,rikima/spark,lxsmnv/spark,JerryLead/spark,markhamstra/spark,wangyum/spark,panfengfeng/spark,xuanyuanking/spark,dhruve/spark,apache/spark,rekhajoshm/spark,rednaxelafx/apache-spark,darionyaphet/spark,MLnick/spark,ahnqirage/spark,darionyaphet/spark,poffuomo/spark,map222/spark,wangmiao1981/spark,WeichenXu123/spark,Aegeaner/spark,maropu/spark,LantaoJin/spark,nlalevee/spark,bOOm-X/spark,apache/spark,publicRoman/spark,yanboliang/spark,esi-mineset/spark,icexelloss/spark,holdenk/spark,goldmedal/spark,aokolnychyi/spark,rikima/spark,ConeyLiu/spark,narahari92/spark,srowen/spark,bravo-zhang/spark,witgo/spark,jlopezmalla/spark,nilsgrabbert/spark,lvdongr/spark,dongjoon-hyun/spark,HyukjinKwon/spark,goldmedal/spark,techaddict/spark,mzl9039/spark,WeichenXu123/spark,ptkool/spark,gioenn/xSpark,michalsenkyr/spark,JoshRosen/spark,panfengfeng/spark,icexelloss/spark,cin/spark,apache-spark-on-k8s/spark,kevinyu98/spark,xflin/spark,haowu80s/spark,techaddict/spark,LantaoJin/spark,nilsgrabbert/spark,sureshthalamati/spark,wangmiao1981/spark,xuanyuanking/spark,ahnqirage/spark,eyalfa/spark,saltstar/spark,debugger87/spark,lxsmnv/spark,bdrillard/spark,ericvandenbergfb/spark,skonto/spark,bravo-zhang/spark,saltstar/spark,huang1900/spark,wangmiao1981/spark,ajaysaini725/spark,metamx/spark,sachintyagi22/spark,MLnick/spark,vinodkc/spark,ioana-delaney/spark,goldmedal/spark,nchammas/spark,jiangxb1987/spark,wangyum/spark,xuanyuanking/spark,MLnick/spark,aray/spark,andrewor14/iolap,ajaysaini725/spark,Panos-Bletsos/spark-cost-model-optimizer,jiangxb1987/spark,ajaysaini725/spark,poffuomo/spark,publicRoman/spark,aray/spark,jlopezmalla/spark,minixalpha/spark,ron8hu/spark,eyalfa/spark,jkbradley/spark,jianran/spark,HyukjinKwon/spark,akopich/spark,1haodian/spark,SHASHANKB/spark,zuotingbing/spark,guoxiaolongzte/spark,shubhamchopra/spark,MLnick/spark,hvanhovell/spark,wzhfy/spark,taroplus/spark,kissmetrics/spark,dbtsai/spark,eyalfa/spark,witgo/spark,guoxiaolongzte/spark,mdespriee/spark,rikima/spark,facaiy/spark,panfengfeng/spark,1haodian/spark,patrick-nicholson/spark,UndeadBaneGitHub/spark,sureshthalamati/spark,bOOm-X/spark,andrewor14/spark,poffuomo/spark,akopich/spark,rednaxelafx/apache-spark,gengliangwang/spark,sahilTakiar/spark,kimoonkim/spark,lvdongr/spark,akopich/spark,liyichao/spark,aokolnychyi/spark,janewangfb/spark,janewangfb/spark,SnappyDataInc/spark,kevinyu98/spark,aosagie/spark,dhruve/spark,cloud-fan/spark,MLnick/spark,icexelloss/spark,WindCanDie/spark,eyalfa/spark,big-pegasus/spark,joseph-torres/spark,markhamstra/spark,techaddict/spark,actuaryzhang/spark,SnappyDataInc/spark,Panos-Bletsos/spark-cost-model-optimizer,ron8hu/spark,skonto/spark,hhbyyh/spark,spark-test/spark,jrshust/spark,zhouyejoe/spark,apache-spark-on-k8s/spark,dbtsai/spark,jkbradley/spark,sureshthalamati/spark,janewangfb/spark,haowu80s/spark,HyukjinKwon/spark,michalsenkyr/spark,milliman/spark,bravo-zhang/spark,taroplus/spark,jianran/spark,joseph-torres/spark,alunarbeach/spark,akopich/spark,ueshin/apache-spark,ptkool/spark,dhruve/spark,gioenn/xSpark,aray/spark,JoshRosen/spark,rikima/spark,witgo/spark,dhruve/spark,shubhamchopra/spark,aokolnychyi/spark,liutang123/spark,ajaysaini725/spark,ibm-research-ireland/sparkoscope,actuaryzhang/spark,minixalpha/spark,vinodkc/spark,goldmedal/spark,jlopezmalla/spark,alunarbeach/spark,kimoonkim/spark,facaiy/spark,zzcclp/spark,cin/spark,xuanyuanking/spark,rednaxelafx/apache-spark,lvdongr/spark,esi-mineset/spark,zhouyejoe/spark,adrian-ionescu/apache-spark,LantaoJin/spark,bOOm-X/spark,zzcclp/spark,nlalevee/spark,srowen/spark,tengpeng/spark,sahilTakiar/spark,minixalpha/spark,ptkool/spark,narahari92/spark,lvdongr/spark,publicRoman/spark,metamx/spark,markhamstra/spark,rikima/spark,wangyum/spark,chuckchen/spark,brad-kaiser/spark,jrshust/spark,ericvandenbergfb/spark,yanboliang/spark,someorz/spark,big-pegasus/spark,big-pegasus/spark,loneknightpy/spark,witgo/spark,andrewor14/iolap,zuotingbing/spark,ibm-research-ireland/sparkoscope,huang1900/spark,dbtsai/spark,liutang123/spark,lxsmnv/spark,JoshRosen/spark,rekhajoshm/spark,spark-test/spark,map222/spark,LantaoJin/spark,saltstar/spark,cin/spark,andrewor14/spark,adrian-ionescu/apache-spark,kissmetrics/spark,patrick-nicholson/spark,loneknightpy/spark,andrewor14/spark,panfengfeng/spark,jiangxb1987/spark,jianran/spark,ericvandenbergfb/spark,rezasafi/spark,kissmetrics/spark,liutang123/spark,actuaryzhang/spark,jkbradley/spark,JerryLead/spark,dbtsai/spark,Panos-Bletsos/spark-cost-model-optimizer,hvanhovell/spark,hhbyyh/spark,ddna1021/spark,hvanhovell/spark,highfei2011/spark,adrian-ionescu/apache-spark,kevinyu98/spark,michalsenkyr/spark,tengpeng/spark,szhem/spark,BryanCutler/spark,SnappyDataInc/spark,rezasafi/spark,cloud-fan/spark,SHASHANKB/spark,aray/spark,mike0sv/spark,taroplus/spark,shaneknapp/spark,mahak/spark,jkbradley/spark,apache-spark-on-k8s/spark,MLnick/spark,1haodian/spark,ibm-research-ireland/sparkoscope,big-pegasus/spark,vinodkc/spark,wzhfy/spark,ioana-delaney/spark,szhem/spark,big-pegasus/spark,zero323/spark,milliman/spark,szhem/spark,aokolnychyi/spark,liyichao/spark,publicRoman/spark,michalsenkyr/spark,facaiy/spark,bdrillard/spark,lxsmnv/spark,dongjoon-hyun/spark,jianran/spark,JerryLead/spark,LantaoJin/spark,saturday-shi/spark,ron8hu/spark,rezasafi/spark,saltstar/spark,guoxiaolongzte/spark,SHASHANKB/spark,mdespriee/spark,nilsgrabbert/spark,liyichao/spark,guoxiaolongzte/spark,byakuinss/spark,Aegeaner/spark,huang1900/spark,ddna1021/spark,alunarbeach/spark,xflin/spark,joseph-torres/spark,apache/spark,setjet/spark,lvdongr/spark,tejasapatil/spark,jrshust/spark,jrshust/spark,gengliangwang/spark,poffuomo/spark,SHASHANKB/spark,alunarbeach/spark,WeichenXu123/spark,akopich/spark,sureshthalamati/spark,cloud-fan/spark,highfei2011/spark,kimoonkim/spark,lvdongr/spark,apache-spark-on-k8s/spark,nilsgrabbert/spark,dbtsai/spark,loneknightpy/spark,bdrillard/spark,srowen/spark,ConeyLiu/spark,szhem/spark,zhouyejoe/spark,zuotingbing/spark,metamx/spark,ConeyLiu/spark,kevinyu98/spark,mike0sv/spark,poffuomo/spark,lxsmnv/spark,shuangshuangwang/spark,zzcclp/spark,techaddict/spark,haowu80s/spark,Aegeaner/spark,ibm-research-ireland/sparkoscope,UndeadBaneGitHub/spark,ericvandenbergfb/spark,spark-test/spark,jianran/spark,vinodkc/spark,zuotingbing/spark,jiangxb1987/spark,map222/spark,aokolnychyi/spark,HyukjinKwon/spark,pronix/spark,panfengfeng/spark,nlalevee/spark,kevinyu98/spark,setjet/spark,saturday-shi/spark,markhamstra/spark,chuckchen/spark,SnappyDataInc/spark,setjet/spark,liyichao/spark,BryanCutler/spark,mzl9039/spark,mahak/spark,UndeadBaneGitHub/spark,zzcclp/spark,ptkool/spark,ptkool/spark,hvanhovell/spark,wangmiao1981/spark,xflin/spark,goldmedal/spark,WindCanDie/spark,gioenn/xSpark,nilsgrabbert/spark,srowen/spark,ron8hu/spark,rezasafi/spark,ahnqirage/spark,LantaoJin/spark,lvdongr/spark,tengpeng/spark,ioana-delaney/spark,minixalpha/spark,kiszk/spark,brad-kaiser/spark,patrick-nicholson/spark,1haodian/spark,poffuomo/spark,eyalfa/spark,shuangshuangwang/spark,saltstar/spark,ericvandenbergfb/spark,narahari92/spark,spark-test/spark,icexelloss/spark,mike0sv/spark,esi-mineset/spark,sachintyagi22/spark,szhem/spark,maropu/spark,dhruve/spark,kevinyu98/spark,LantaoJin/spark,maropu/spark,wangyum/spark,Panos-Bletsos/spark-cost-model-optimizer,apache/spark,mzl9039/spark,huang1900/spark,wangmiao1981/spark,michalsenkyr/spark,andrewor14/iolap,gengliangwang/spark,cin/spark,hvanhovell/spark,metamx/spark,aray/spark,taroplus/spark,shuangshuangwang/spark,1haodian/spark,saltstar/spark,michalsenkyr/spark,xuanyuanking/spark,ddna1021/spark,loneknightpy/spark,brad-kaiser/spark,JerryLead/spark,ddna1021/spark,big-pegasus/spark,janewangfb/spark,UndeadBaneGitHub/spark,sureshthalamati/spark,someorz/spark,tejasapatil/spark,witgo/spark,zhouyejoe/spark,markhamstra/spark,jkbradley/spark,mzl9039/spark,chuckchen/spark,maropu/spark,map222/spark,someorz/spark,xflin/spark,kissmetrics/spark,tengpeng/spark,brad-kaiser/spark,shuangshuangwang/spark,spark-test/spark,andrewor14/spark,BryanCutler/spark,ahnqirage/spark,HyukjinKwon/spark,darionyaphet/spark,JoshRosen/spark,dbtsai/spark,ioana-delaney/spark,liutang123/spark,pronix/spark,gengliangwang/spark,liutang123/spark,yanboliang/spark,jrshust/spark,shaneknapp/spark,taroplus/spark,eyalfa/spark,pronix/spark,BryanCutler/spark,shuangshuangwang/spark,UndeadBaneGitHub/spark,matthewfranglen/spark,milliman/spark,dongjoon-hyun/spark,byakuinss/spark,SnappyDataInc/spark,esi-mineset/spark,someorz/spark,kissmetrics/spark,kimoonkim/spark,ueshin/apache-spark,ron8hu/spark,icexelloss/spark,WindCanDie/spark,zzcclp/spark,darionyaphet/spark,highfei2011/spark,liyichao/spark,narahari92/spark,holdenk/spark,mzl9039/spark,andrewor14/iolap,xuanyuanking/spark,zero323/spark,patrick-nicholson/spark,ericvandenbergfb/spark,shaneknapp/spark,rezasafi/spark,andrewor14/spark,ahnqirage/spark,alunarbeach/spark,patrick-nicholson/spark,zuotingbing/spark,chuckchen/spark,dongjoon-hyun/spark,rikima/spark,someorz/spark,shubhamchopra/spark,gioenn/xSpark,tengpeng/spark,cloud-fan/spark,sureshthalamati/spark,bravo-zhang/spark,yanboliang/spark,andrewor14/spark,aray/spark,pronix/spark,bdrillard/spark,dongjoon-hyun/spark,icexelloss/spark,nlalevee/spark,someorz/spark