Google Git
Sign in
googlers / jrn / git / 0db71e0fa94c1857f98890928098e8f4c8ac6f26
commit0db71e0fa94c1857f98890928098e8f4c8ac6f26[log] [tgz]
authorRené Scharfe <rene.scharfe@lsrfire.ath.cx>Sun Apr 01 00:10:11 2012 +0200
committerJunio C Hamano <gitster@pobox.com>Wed Apr 11 08:50:53 2012 -0700
tree0095038b4c0b0c9d643380f479cb17db1dcd14a6
parent828ea97de486c1693d6e4f2c7347acb50235a85d [diff]
add mergesort() for linked lists

This adds a generic bottom-up mergesort implementation for singly linked
lists.  It was inspired by Simon Tatham's webpage on the topic[1], but
not so much by his implementation -- for no good reason, really, just a
case of NIH.

[1] http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html

Signed-off-by: Rene Scharfe <rene.scharfe@lsrfire.ath.cx>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
5 files changed
tree: 0095038b4c0b0c9d643380f479cb17db1dcd14a6
  1. block-sha1/
  2. builtin/
  3. compat/
  4. contrib/
  5. Documentation/
  6. git-gui/
  7. git_remote_helpers/
  8. gitk-git/
  9. gitweb/
  10. mergetools/
  11. perl/
  12. po/
  13. ppc/
  14. t/
  15. templates/
  16. vcs-svn/
  17. xdiff/
  18. RelNotes ⇨ Documentation/RelNotes/1.7.9.txt
  19. .gitattributes
  20. .gitignore
  21. .mailmap
  22. abspath.c
  23. aclocal.m4
  24. advice.c
  25. advice.h
  26. alias.c
  27. alloc.c
  28. archive-tar.c
  29. archive-zip.c
  30. archive.c
  31. archive.h
  32. argv-array.c
  33. argv-array.h
  34. attr.c
  35. attr.h
  36. base85.c
  37. bisect.c
  38. bisect.h
  39. blob.c
  40. blob.h
  41. branch.c
  42. branch.h
  43. builtin.h
  44. bulk-checkin.c
  45. bulk-checkin.h
  46. bundle.c
  47. bundle.h
  48. cache-tree.c
  49. cache-tree.h
  50. cache.h
  51. check-builtins.sh
  52. check-racy.c
  53. check_bindir
  54. color.c
  55. color.h
  56. combine-diff.c
  57. command-list.txt
  58. commit.c
  59. commit.h
  60. config.c
  61. config.mak.in
  62. configure.ac
  63. connect.c
  64. connected.c
  65. connected.h
  66. convert.c
  67. convert.h
  68. copy.c
  69. COPYING
  70. credential-cache--daemon.c
  71. credential-cache.c
  72. credential-store.c
  73. credential.c
  74. credential.h
  75. csum-file.c
  76. csum-file.h
  77. ctype.c
  78. daemon.c
  79. date.c
  80. decorate.c
  81. decorate.h
  82. delta.h
  83. diff-delta.c
  84. diff-lib.c
  85. diff-no-index.c
  86. diff.c
  87. diff.h
  88. diffcore-break.c
  89. diffcore-delta.c
  90. diffcore-order.c
  91. diffcore-pickaxe.c
  92. diffcore-rename.c
  93. diffcore.h
  94. dir.c
  95. dir.h
  96. editor.c
  97. entry.c
  98. environment.c
  99. exec_cmd.c
  100. exec_cmd.h
  101. fast-import.c
  102. fetch-pack.h
  103. fixup-builtins
  104. fmt-merge-msg.h
  105. fsck.c
  106. fsck.h
  107. generate-cmdlist.sh
  108. gettext.c
  109. gettext.h
  110. git-add--interactive.perl
  111. git-am.sh
  112. git-archimport.perl
  113. git-bisect.sh
  114. git-compat-util.h
  115. git-cvsexportcommit.perl
  116. git-cvsimport.perl
  117. git-cvsserver.perl
  118. git-difftool--helper.sh
  119. git-difftool.perl
  120. git-filter-branch.sh
  121. git-instaweb.sh
  122. git-lost-found.sh
  123. git-merge-octopus.sh
  124. git-merge-one-file.sh
  125. git-merge-resolve.sh
  126. git-mergetool--lib.sh
  127. git-mergetool.sh
  128. git-parse-remote.sh
  129. git-pull.sh
  130. git-quiltimport.sh
  131. git-rebase--am.sh
  132. git-rebase--interactive.sh
  133. git-rebase--merge.sh
  134. git-rebase.sh
  135. git-relink.perl
  136. git-remote-testgit.py
  137. git-repack.sh
  138. git-request-pull.sh
  139. git-send-email.perl
  140. git-sh-i18n.sh
  141. git-sh-setup.sh
  142. git-stash.sh
  143. git-submodule.sh
  144. git-svn.perl
  145. GIT-VERSION-GEN
  146. git-web--browse.sh
  147. git.c
  148. git.spec.in
  149. gpg-interface.c
  150. gpg-interface.h
  151. graph.c
  152. graph.h
  153. grep.c
  154. grep.h
  155. hash.c
  156. hash.h
  157. help.c
  158. help.h
  159. hex.c
  160. http-backend.c
  161. http-fetch.c
  162. http-push.c
  163. http-walker.c
  164. http.c
  165. http.h
  166. ident.c
  167. imap-send.c
  168. INSTALL
  169. kwset.c
  170. kwset.h
  171. levenshtein.c
  172. levenshtein.h
  173. LGPL-2.1
  174. list-objects.c
  175. list-objects.h
  176. ll-merge.c
  177. ll-merge.h
  178. lockfile.c
  179. log-tree.c
  180. log-tree.h
  181. mailmap.c
  182. mailmap.h
  183. Makefile
  184. match-trees.c
  185. merge-file.c
  186. merge-file.h
  187. merge-recursive.c
  188. merge-recursive.h
  189. mergesort.c
  190. mergesort.h
  191. name-hash.c
  192. notes-cache.c
  193. notes-cache.h
  194. notes-merge.c
  195. notes-merge.h
  196. notes.c
  197. notes.h
  198. object.c
  199. object.h
  200. pack-check.c
  201. pack-refs.c
  202. pack-refs.h
  203. pack-revindex.c
  204. pack-revindex.h
  205. pack-write.c
  206. pack.h
  207. pager.c
  208. parse-options-cb.c
  209. parse-options.c
  210. parse-options.h
  211. patch-delta.c
  212. patch-ids.c
  213. patch-ids.h
  214. path.c
  215. pkt-line.c
  216. pkt-line.h
  217. preload-index.c
  218. pretty.c
  219. progress.c
  220. progress.h
  221. prompt.c
  222. prompt.h
  223. quote.c
  224. quote.h
  225. reachable.c
  226. reachable.h
  227. read-cache.c
  228. README
  229. reflog-walk.c
  230. reflog-walk.h
  231. refs.c
  232. refs.h
  233. remote-curl.c
  234. remote.c
  235. remote.h
  236. replace_object.c
  237. rerere.c
  238. rerere.h
  239. resolve-undo.c
  240. resolve-undo.h
  241. revision.c
  242. revision.h
  243. run-command.c
  244. run-command.h
  245. send-pack.h
  246. sequencer.c
  247. sequencer.h
  248. server-info.c
  249. setup.c
  250. sh-i18n--envsubst.c
  251. sha1-array.c
  252. sha1-array.h
  253. sha1-lookup.c
  254. sha1-lookup.h
  255. sha1_file.c
  256. sha1_name.c
  257. shallow.c
  258. shell.c
  259. shortlog.h
  260. show-index.c
  261. sideband.c
  262. sideband.h
  263. sigchain.c
  264. sigchain.h
  265. strbuf.c
  266. strbuf.h
  267. streaming.c
  268. streaming.h
  269. string-list.c
  270. string-list.h
  271. submodule.c
  272. submodule.h
  273. symlinks.c
  274. tag.c
  275. tag.h
  276. tar.h
  277. test-chmtime.c
  278. test-credential.c
  279. test-ctype.c
  280. test-date.c
  281. test-delta.c
  282. test-dump-cache-tree.c
  283. test-genrandom.c
  284. test-index-version.c
  285. test-line-buffer.c
  286. test-match-trees.c
  287. test-mergesort.c
  288. test-mktemp.c
  289. test-obj-pool.c
  290. test-parse-options.c
  291. test-path-utils.c
  292. test-run-command.c
  293. test-scrap-cache-tree.c
  294. test-sha1.c
  295. test-sha1.sh
  296. test-sigchain.c
  297. test-string-pool.c
  298. test-subprocess.c
  299. test-svn-fe.c
  300. test-treap.c
  301. thread-utils.c
  302. thread-utils.h
  303. trace.c
  304. transport-helper.c
  305. transport.c
  306. transport.h
  307. tree-diff.c
  308. tree-walk.c
  309. tree-walk.h
  310. tree.c
  311. tree.h
  312. unimplemented.sh
  313. unix-socket.c
  314. unix-socket.h
  315. unpack-trees.c
  316. unpack-trees.h
  317. upload-pack.c
  318. url.c
  319. url.h
  320. usage.c
  321. userdiff.c
  322. userdiff.h
  323. utf8.c
  324. utf8.h
  325. walker.c
  326. walker.h
  327. wrap-for-bin.sh
  328. wrapper.c
  329. write_or_die.c
  330. ws.c
  331. wt-status.c
  332. wt-status.h
  333. xdiff-interface.c
  334. xdiff-interface.h
  335. zlib.c