Skip to content

Instantly share code, notes, and snippets.

@erika-dike

erika-dike/mergesort.py

Created July 3, 2018 11:30
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save erika-dike/5eb10230cbf229b26a52a9d1df8ed490 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save erika-dike/5eb10230cbf229b26a52a9d1df8ed490 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. Chukwuerika Dike created this gist Jul 3, 2018.
    29 changes: 29 additions & 0 deletions mergesort.py
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,29 @@
    def merge_sort(alist):
    if len(alist) > 1:
    mid = len(alist) // 2
    lefthalf = alist[:mid]
    righthalf = alist[mid:]

    merge_sort(lefthalf)
    merge_sort(righthalf)

    i = j = k = 0

    while i < len(lefthalf) and j < len(righthalf):
    if lefthalf[i] < righthalf[j]:
    alist[k] = lefthalf[i]
    i += 1
    else:
    alist[k] = righthalf[j]
    j += 1
    k += 1

    while i < len(lefthalf):
    alist[k] = lefthalf[i]
    i += 1
    k += 1

    while j < len(righthalf):
    alist[k] = righthalf[j]
    j += 1
    k += 1